Herhangi Matematiksel Şeyler: Euler Projesi 230. Soru

Fibonacci Kelimeleri

Herhangi iki A and B rakam dizisi için içindeki her terim önceki ikisinin birleşimi olan F_A,B dizisini (A,B,AB,BAB,ABBAB,...) biçiminde tanımlayalım.

Dahası D_A,B(n), F_A,B dizisinin en az n basamağı bulunan ilk teriminin n. basamağı olsun.

Örnek:
A=1415926535, B=8979323846 olsun. D_A,B(35) bulmak için:
F_A,B dizisinin ilk birkaç terimi:
1415926535
8979323846
14159265358979323846
897932384614159265358979323846
14159265358979323846897932384614159265358979323846
Bu durumda D_A,B(35), 5. terimdeki 35. basamaktır: 9.

Şimdi A için π sayısının ilk 100 ondalık basamağını alalım:
14159265358979323846264338327950288419716939937510
58209749445923078164062862089986280348253421170679
ve B için sonraki 100 basamağı:
82148086513282306647093844609550582231725359408128
48111745028410270193852110555964462294895493038196 .
∑_{n = 0,1,...,17} 10ⁿ× D_A,B((127+19n)×7ⁿ) kaçtır?

Cevap: 850481152593119296

Python:

def e(a, b, i):
 la, lb = len(a), len(b)
 if i < la: return a[i]
 if i < la+lb: return b[i-la]
 
 t = 2*(la+lb)
 x, y = lb, la+lb
 k = 2
 while t <= i:
  x, y = y, x+y
  t += y
  k += 1
 
 i = i-(t-y)
 y, x = x, y-x
 
 while k > 1:
  if i >= x:
   k -= 1
   i -= x
  else:
   k -= 2
   y, x = x, y-x
  
  y, x = x, y-x
 
 if k == 0: return a[i]
 return b[i]

def d(a, b, i):
 la, lb = len(a), len(b)
 if i < la: return a[i]
 if i < lb: return b[i]
 
 x, y = lb, la+lb
 k = 2
 while y <= i:
  x, y = y, x+y
  k += 1
 
 y, x = x, y-x
 while k > 1:
  if i >= x:
   k -= 1
   i -= x
  else:
   k -= 2
   y, x = x, y-x
  
  y, x = x, y-x
 
 if k == 0: return a[i]
 return b[i]

s = '1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679'
t = '8214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196'

ans = 0
for n in range(0, 17+1):
 ans += int(d(s, t, (127+19*n)*7**n-1))*10**n

print(ans)

C++:

#include <stdio.h>
#include <math.h>
#include <vector>
#include <string>
using namespace std;
long long int A;
long long int B;
long long int array[1000];
long long int powsev(int x);

vector <long long int> findit(long long int A,long long int B,int id,long long int pos);
string aarr="1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679";
string barr="8214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196"; 
int main()
{
  A=100;
  B=100;
  array[1]=A;
  array[2]=B;
 
  for(int i=17;i>=0;i--)
    {
      long long finval=(127+19*i)*powsev(i);
       int ival=2;
       do
  {
    ival++;
    array[ival]=array[ival-1]+array[ival-2];
  }while(array[ival]<finval);
      vector <long long int> retval=findit(A,B,ival,finval);
      if(retval[0]==1)
 printf("%c",aarr[retval[1]-1]);
      else
 printf("%c",barr[retval[1]-1]);
    }
  printf("\n");
  
}

long long int powsev(int x)
{
  if(x==0)
    return 1;

  else
    return 7*powsev(x-1);
}

vector <long long int> findit(long long int A,long long int B,int id,long long int pos)
{
  if(id==1 || id==2)
    {
      vector <long long int> a;
      a.resize(2);
      a[0]=id;
      a[1]=pos;
      return a;
    }
  if(pos>array[id-2])
    {
      return findit(A,B,id-1,pos-array[id-2]);
    }
  else
    return findit(A,B,id-2,pos);
}

Mathematica:

U = Rest@First@RealDigits[Pi, 10, 201];
A = Take[U, {1, 100}]; B = Take[U, {101, 200}];
F[n_] := F[n] = F[n-1] + F[n-2];
F[1]=Length@A; F[2]=Length@B; F[0]=F[-1]=0;
d[m_] := Module[{i, k = m},
      For[i = 1, F[i] < k, i++];
      For[, i > 0, i--, If[k <= F[i-2], i--, k-=F[i-2]] ];
      Return[If[i<0,A,B][[k]]];
];
Sum[d[(127 + 19i)*7^i]*10^i, {i, 0, 17}]

Java:


static private int digit(BigInteger n)
{
  // find the n'th digit in the first term containing at least n digits
  int i = 1;
  while (length[i].compareTo(n) < 0) ++i;
  return digit(i,n);
}

static private int digit(int i, BigInteger n)
{
  // find the n'th digit in the i'th term

  if (i == 1) return A[n.intValue()];
  if (i == 2) return B[n.intValue()];

  if (n.compareTo(length[i-2]) <= 0) return digit(i-2,n);
  else return digit(i-1,n.subtract(length[i-2]));
}

Ruby:

sa="1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679"
sb="8214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196"
res=[]
ff=[1,1]
(0..17).each{|n|
  n=(127+19*n)*7**n-1
  q,r=n.divmod(100)
  q+=1
  ff<<ff[-2]+ff[-1] while ff[-1]<q
  fi=ff.length-1
  while fi>2
    if q>ff[fi-2]
      q-=ff[fi-2]
      fi-=1
    else
      fi-=2
    end
  end
  if q!=fi
    res<<sa[r..r]
  else
    res<<sb[r..r]
  end
}
p res.reverse.to_s

Herhangi Matematiksel Şeyler

Sayfalar

29 Temmuz 2017

Euler Projesi 230. Soru