题目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位继续。

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

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

329468
[Finished in 5.1s]

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()

芒果加黄桃

算的好慢...

永恒的蓝色梦想

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')

结果不明








[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

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