欧拉计划 发表于 2016-8-17 21:58:36

题目104：找出前九位和后九位数字为pandigital的斐波那契数

本帖最后由 欧拉计划 于 2016-8-17 22:24 编辑

Pandigital Fibonacci ends

The Fibonacci sequence is defined by the recurrence relation:



It turns out thatwhich contains 113 digits, is the first Fibonacci number for which the last nine digits are 1-9 pandigital (contain all the digits 1 to 9, but not necessarily in order). Andwhich contains 575 digits, is the first Fibonacci number for which the first nine digits are 1-9 pandigital.

Given thatis the first Fibonacci number for which the first nine digits AND the last nine digits are 1-9 pandigital, find k.

题目：

斐波那契数列可以用一个递归关系来定义：

其中 ，

事实证明， 一个包含 113 位数字的数，是第一个后九位数字都是 pandigital（包含 1 到 9 的所有数字，但未必按照顺序）的斐波那契数。 而 包含 575 位数字，是第一个前九位数字是 pandigital的斐波那契数。

若是第一个前九位数和后九位数都是pandigital的斐波那契数，求 k。


jerryxjr1220 发表于 2016-9-28 00:25:35

程序是有了并通过了验算，但是我算到斐波那契数列的第14000位了都还没找到。。。
有兴趣的同学可以继续算下去，只需修改程序中的倒数第4行的值就能直接从数列的后XX位继续。
def isPandigital(num):
        flag = 0
        if len(str(num)) > 9:
                lst1 = str(num)[:9]
                lst2 = str(num)[-9:]
                lst1 = set(lst1)
                lst2 = set(lst2)
                if len(lst1) == 9 and '0' not in lst1:
                        if len(lst2) == 9 and '0' not in lst2:
                                flag = 1
        return flag

a = 1
b = 1
count = 2
while 1:
        c = a + b
        a = b
        b = c
        count += 1
        if count % 10000 == 0:
                print(count)
        if count > 140000:
                if isPandigital(c) == 1:
                        print (count)
                        exit()

jerryxjr1220 发表于 2016-10-21 20:59:39

还是上面的代码，稍微做了点改动，优化了算法。
329468

def isPandigital(num):
      s = set(str(num))
      if len(s) == 9 and '0' not in s:
                return True
      else:
                return False

a = 1
b = 1
count = 2
while 1:
      c = a + b
      a = b
      b = c
      count += 1
      if count > 300000:
                clast = c%(10**9)
                if isPandigital(clast):
                        if isPandigital(str(c)[:9]):
                              print (count)
                              exit()

芒果加黄桃 发表于 2017-3-17 16:46:02

算的好慢...

永恒的蓝色梦想 发表于 2019-7-24 01:22:16

本帖最后由 永恒的蓝色梦想 于 2021-2-11 16:24 编辑

from time import process_time as t
t1=t()
def ip(n):
        if '0' in n or len(set(n))!=9:return False
        return True
def fib():
        a,b=1,1
        while 1:
                a,b=b,a+b
                yield str(b)
for i in fib():
        if len(i)<=575:continue
        if ip(i[:9])and ip(i[-9:]):break
print(f'运行结果：{str(count)}\n运行时间：{t()-t1}s')
结果不明








#include<iostream>
#include<string>



bool judge(const vector<unsigned char>& s)noexcept {
    char* str;
    unsigned char n;
    union {
      unsigned char digits;
      struct {
            unsigned long long a;
            unsigned short b;
      } x;
    } x;


    str = s.c_str();
    x.x.b = x.x.a = 0;

    for (n = 9; n; n--) {
      x.digits[*str]++;
      str++;
    }

    if ((x.x.a - (unsigned long long)0b0000000100000001000000010000000100000001000000010000000100000001) & (x.x.b - (unsigned short)0b100000001)) {
      return false;
    }


    str = s.c_str();
void add(vector<unsigned char>& a, const vector<unsigned char>& b)noexept {
    size_t n;

    for (n = b.size() - a.size(); n; n--) {
      a.push_back('0');
    }

    for (n = 0; n < a.size() - 1;) {
      a += b;

      if (a > 9) {
            a -= 10;
            a[++n]++;
    }
}

   
int main() {
    using namespace std;
    ios::sync_with_stdio(false);

    vector<unsigned char> a = { 1 }, b = { 1 };


    while (a.size() <= 18) {
      add(a, b);
      swap(a, b);
    }

    for (;;) {
    }
}

guosl 发表于 2020-4-7 10:18:54

调用mpir库
//答案：329468
#include <iostream>
#include <algorithm>
#include <mpirxx.h>
#include <string>
using namespace std;

int main(void)
{
mpz_class f1 = 1, f2 = 1, f3;
int k = 3;
while (true)
{
    f3 = f2 + f1;
    string str = f3.get_str(10);
    if (str.length() >= 18)
    {
      string s = str.substr(str.length() - 9, 9);
      sort(s.begin(), s.end());
      if (s.compare("123456789") == 0)
      {
      s = str.substr(0, 9);
      sort(s.begin(), s.end());
      if (s.compare("123456789") == 0)
          break;
      }
    }
    f1 = f2;
    f2 = f3;
    ++k;
}
cout << k << endl;
return 0;
}

fc1735 发表于 2023-8-31 03:16:13

ah, al = 1, 1
bh, bl = 1, 1

for i in range(3, 9999999999999999):
bl += al
al = bl - al
bl %= int(1e9)
al %= int(1e9)

bh += ah
ah = bh - ah
sh, sl = str(bh), str(bl)
if len(sh) > 20:
    bh //= 10
    ah //= 10

if ''.join(sorted(sl)) == '123456789' and ''.join(sorted(sh[:9])) == '123456789':
    print(i)
    break
页: [1]
查看完整版本: 题目104：找出前九位和后九位数字为pandigital的斐波那契数