Euler Projesi 277. Soru

Uyarlanmış Bir Collatz Dizisi

Bir $a_1$ başlama değeri ile uyarlanmış bir Collatz dizisi aşağıdaki şekilde elde edilir:
$a_{n+1}=\frac{a_n}{3}$, eğer $a_n$ 3'ün katıysa. Bunu aşağı yönlü büyük bir "D" adımı olarak belirteceğiz.
$a_{n+1}=\frac{4a_{n}+2}{3}$, eğer $a_n$'nin 3'le bölümünden kalan 1 ise. Bunu yukarı yönlü bir "U" adımı olarak belirteceğiz.
$a_{n+1}=\frac{2a_{n}-1}{3}$, eğer $a_n$'nin 3'le bölümünden kalan 2 ise. Bunu aşağı yönlü küçük bir "U" adımı olarak belirteceğiz.
$a_n=1$ olduğunda ise dizi sonlanacak.
Herhangi bir tam sayı ile başlayıp adım dizisini oluşturabiliriz.
Örneğin $a_1=231$ ise dizi $(a_n)=\{231,77,51,17,11,7,10,14,9,3,1\}$ ve karşılık gelen adım dizisi "DdDddUUdDD" olur.
Elbette aynı "DdDddUUdDD" adım dizisi ile başlayan başka diziler de mevcuttur.
Örneğin $a_1=1004064$ ise adım dizisi "DdDddUUdDDDdUDUUUdDdUUDDDUdDD" olur.
Aslında  DdDddUUdDD ile başlayan olası en küçük $a_1>10^6$ sayısı 1004064'tür.

UDDDUdddDDUDDddDdDddDDUDDdUUDd ile başlayan olası en küçük $a_1>10^{15}$ sayısı kaçtır?
Cevap: 1125977393124310Python: #! /usr/bin/env python from number import crt op = "UDDDUdddDDUDDddDdDddDDUDDdUUDd"[::-1] def zero(x): return [3*y for y in x] def one(x): return [y/4 for y in crt(0, 4, 3*x[1] - 2, 3*x[0])[::-1]] def two(x): return [y/2 for y in crt(0, 2, 3*x[1] + 1, 3*x[0])[::-1]] ops = {'D': zero, 'U': one, 'd': two } def apply(op, a): if not op: return a return apply(op[1:], ops[op[0]](a)) lol = apply(op, (1,0)) a = (10**15 / lol[0] + 1) * lol[0] + lol[1] print a C/C++: __int64 prob277(void) { char *seq="UDDDUdddDDUDDddDdDddDDUDDdUUDd"; __int64 p,q,n, ip, o, f; int i, l=strlen(seq); // define a(x) = (p*a0+q)/n p=n=1; q=0; for(i=0;i<l;i++){ switch(seq[i]){ case 'D': n*=3; break; case 'U': p*=4; q=4*q+2*n; n*=3; break; case 'd': p*=2; q=2*q-n; n*=3; break; } } ip=nt->modinverse(p,n); // ip=inverse of p (mod n) o=nt->modproduct(ip,-q,n); // offset = ip*(-q) (mod n) f=(1000000000000000-o)/n + 1; // factor = floor((10^15-offset)/n) + 1 return(o+f*n); // result = offset + factor*n } Java: package pe277; import java.util.ArrayList; import java.util.HashSet; /** * * @author Jackson */ public class Main { /** * @param args the command line arguments */ public static void main(String[] args) { ArrayList<long> possibles = new ArrayList<long>(); String digs = "UDDDUdddDDUDDddDdDddDDUDDdUUDd"; long curtop = 3; long top = 1000000000000000L; possibles.add(3L); possibles.add(2L); possibles.add(1L); for(int i = 0; i < digs.length();i++) { ArrayList<Long> newpossibles = new ArrayList<long>(); for(int r = 0; r <possibles.size();r++) newpossibles.add(possibles.get(r)); for(int k = 0; k<i;k++) { if(digs.charAt(k) == "D".charAt(0)) for(int r = 0; r <possibles.size();r++) { if(newpossibles.get(r)>0 && newpossibles.get(r)%3==0) newpossibles.set(r,newpossibles.get(r)/3); else newpossibles.set(r, -1L); } if(digs.charAt(k) == "d".charAt(0)) for(int r = 0; r <possibles.size();r++) { if(newpossibles.get(r)>0 && newpossibles.get(r)%3==2) newpossibles.set(r,(2*newpossibles.get(r)-1)/3); else newpossibles.set(r, -1L); } if(digs.charAt(k) == "U".charAt(0)) for(int r = 0; r <possibles.size();r++) { if(newpossibles.get(r)>0 && newpossibles.get(r)%3==1) newpossibles.set(r,(4*newpossibles.get(r)+2)/3); else newpossibles.set(r, -1L); } } for(int r = 0; r<possibles.size();r++) { if((digs.charAt(i) == "D".charAt(0) && newpossibles.get(r) %3!=0 )|| ! (newpossibles.get(r)>0 )) possibles.set(r, -1L); if((digs.charAt(i) == "U".charAt(0) && newpossibles.get(r) %3!=1) || ! (newpossibles.get(r)>0)) possibles.set(r, -1L); if((digs.charAt(i) == "d".charAt(0) && newpossibles.get(r) %3!=2) || ! (newpossibles.get(r)>0)) possibles.set(r, -1L); } newpossibles.clear(); HashSet<long> newvals = new HashSet<long>(); for(int r = 0; r <possibles.size();r++) { if(possibles.get(r)>=0) { for(int c = 0; c<=i;c++) { newvals.add((possibles.get(r))); newvals.add((possibles.get(r)+power3(c+1))); newvals.add((possibles.get(r)+2*power3(c+1))); } } } possibles.clear(); possibles.addAll(newvals); } long min = power3(digs.length()+3); for(long v:possibles) { long g = v; if(g>0) { while(g<top) g+=power3(digs.length()+1); if(g<min ) { min=g; System.out.println(g); } } } } public static long power3(int n) { long a = 1; for(int i = 0;i<n;i++) a*=3; return a; } ml: let rec main s n = let rec loop i m = if i = String.length s then n else let next = match s.[i] with | 'D' -> m | 'U' -> 4. *. m +. 2. | _ -> 2. *. m -. 1. in if mod_float next 3. = 0. then loop (i+1) (next /. 3.) else main s (n +. 3. ** float i) in loop 0 n ;; Printf.printf "Answer: %.f\n" (main Sys.argv.(1) 1e15) } Haskell: import System (getArgs) euler277 n s = loop n 1 s where loop m k [] = n loop m k (x:xs) | next `mod` 3 == 0 = loop (next `div` 3) (k * 3) xs | otherwise = euler277 (n + k) s where next | x == 'D' = m | x == 'U' = 4 * m + 2 | x == 'd' = 2 * m - 1 main = getArgs >>= print . euler277 (10^15) . head Delphi: program mathC277; uses sysutils, windows; function reverseSequence(s: string; var n, n0: int64): boolean; var i, j, L: integer; fault: boolean; m: int64; c: char; begin fault:= false; for j:= n0 to 100000000 do begin n:= j; n0:= j; fault:= false; L:= length(s); for i:= 1 to length(s) do begin c:= s[L]; dec(L); case c of 'U': begin m:= 3*n-2; if m mod 4<>0 then begin fault:= true; break; end; n:= m div 4; end; 'D': n:= 3*n; 'd': begin m:= 3*n+1; if m mod 2<>0 then begin fault:= true; break; end; n:= m div 2; end; end (* case *); end(* for i *); if not fault then break; end; result:= not fault; end; var s, sn: string; n, n0: int64; begin s:= 'UDDDUdddDDUDDddDdDddDDUDDdUUDd'; n0:= 0; repeat n0:= n0+1; if not reverseSequence(s, n, n0) then writeln('still fault s'); until n>1000000000000000; str(n:17,sn); writeln('n '+sn); end.