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

欧拉计划

Pandigital Fibonacci ends

The Fibonacci sequence is defined by the recurrence relation:



It turns out that which 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). And which contains 575 digits, is the first Fibonacci number for which the first nine digits are 1-9 pandigital.

Given that is 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

程序是有了并通过了验算，但是我算到斐波那契数列的第14000位了都还没找到。。。
有兴趣的同学可以继续算下去，只需修改程序中的倒数第4行的值就能直接从数列的后XX位继续。

1. def isPandigital(num):
   
2.         flag = 0
   
3.         if len(str(num)) > 9:
   
4.                 lst1 = str(num)[:9]
   
5.                 lst2 = str(num)[-9:]
   
6.                 lst1 = set(lst1)
   
7.                 lst2 = set(lst2)
   
8.                 if len(lst1) == 9 and '0' not in lst1:
   
9.                         if len(lst2) == 9 and '0' not in lst2:
   
10.                                 flag = 1
    
11.         return flag
    
12. 
    
13. a = 1
    
14. b = 1
    
15. count = 2
    
16. while 1:
    
17.         c = a + b
    
18.         a = b
    
19.         b = c
    
20.         count += 1
    
21.         if count % 10000 == 0:
    
22.                 print(count)
    
23.         if count > 140000:
    
24.                 if isPandigital(c) == 1:
    
25.                         print (count)
    
26.                         exit()

复制代码

jerryxjr1220

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

1. 329468
   
2. [Finished in 5.1s]

复制代码

1. def isPandigital(num):
   
2.         s = set(str(num))
   
3.         if len(s) == 9 and '0' not in s:
   
4.                 return True
   
5.         else:
   
6.                 return False
   
7. 
   
8. a = 1
   
9. b = 1
   
10. count = 2
    
11. while 1:
    
12.         c = a + b
    
13.         a = b
    
14.         b = c
    
15.         count += 1
    
16.         if count > 300000:
    
17.                 clast = c%(10**9)
    
18.                 if isPandigital(clast):
    
19.                         if isPandigital(str(c)[:9]):
    
20.                                 print (count)
    
21.                                 exit()

复制代码

芒果加黄桃

算的好慢...

永恒的蓝色梦想

1. from time import process_time as t
   
2. t1=t()
   
3. def ip(n):
   
4.         if '0' in n or len(set(n))!=9:return False
   
5.         return True
   
6. def fib():
   
7.         a,b=1,1
   
8.         while 1:
   
9.                 a,b=b,a+b
   
10.                 yield str(b)
    
11. for i in fib():
    
12.         if len(i)<=575:continue
    
13.         if ip(i[:9])and ip(i[-9:]):break
    
14. print(f'运行结果：{str(count)}\n运行时间：{t()-t1}s')

复制代码

结果不明








[code]#include<iostream>
#include<string>



bool judge(const vector<unsigned char>& s)noexcept {
    char* str;
    unsigned char n;
    union {
        unsigned char digits[10];
        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[n] += b[n];

        if (a[n] > 9) {
            a[n] -= 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

调用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

1. ah, al = 1, 1
   
2. bh, bl = 1, 1
   
3. 
   
4. for i in range(3, 9999999999999999):
   
5.   bl += al
   
6.   al = bl - al
   
7.   bl %= int(1e9)
   
8.   al %= int(1e9)
   
9. 
   
10.   bh += ah
    
11.   ah = bh - ah
    
12.   sh, sl = str(bh), str(bl)
    
13.   if len(sh) > 20:
    
14.     bh //= 10
    
15.     ah //= 10
    
16. 
    
17.   if ''.join(sorted(sl)) == '123456789' and ''.join(sorted(sh[:9])) == '123456789':
    
18.     print(i)
    
19.     break

复制代码