Euler Projesi 225. Soru

Tribonacci bölmeyenleri

1, 1, 1, 3, 5, 9, 17, 31, 57, 105, 193, 355, 653, 1201 ... dizisi $T_1=T_2=T_3=1$ ve $T_n=T_{n-1}+T_{n-2}+T_{n-3}$ şeklinde tanımlanıyor.
Şimdi 27 sayısının bu dizinin hiçbir terimini bölmeyeceği gösterilebilir.
Aslında 27 sayısı bu özelliğe sahip ilk sayıdır.

Yukarıdaki dizinin hiçbir terimini bölmeyen 124. tek sayıyı bulunuz.

Cevap: 2009
C++:

#include <stdio.h>

int main()
{
    int s1,s2,s3,N=1,ct=0,temp,found;
 
 while(ct<124)  {
    N+=2;
    s1=1,s2=1,s3=3;
    found=0;
    while((s1!=1)||(s2!=1)||(s3!=1))  {
        temp=(s1+s2+s3)%N;
     s1=s2;
     s2=s3;
     s3=temp;
     if(s3%N==0)  {
     found=1;
     break;
     }
    }
    if(found==0)  {
    ct++;
    printf("%d-th term=%d\n",ct,N);
    }
 }
 return 0;
}

Java:

public class Euler225 {

 static boolean test(int m) {
  int a1 = 1, b1 = 1, c1 = 1;
  int a2 = 1, b2 = 1, c2 = 1;
  
  do {
   int d1 = (a1 + b1 + c1) % m;
   if(d1 == 0) return false;
   int d2 = (a2 + b2 + c2 + b2 + c2) % m;
   a1 = b1; b1 = c1; c1 = d1;
   b2 = (a2 + b2 + c2) % m; a2 = c2;  c2 = d2;
  } while(a1 != a2 || b1 != b2 || c1 != c2);
  return true;
 }
 public static void main(String[] args) {
  int t = 1;
  int todo = 124;
  while(todo > 0) {
   t += 2;
   if(test(t)) todo--;
  }
  System.out.println(t);

 }

}

Python:

internal static long solve(int l)
        {
            var trib = new List<long> { 1, 1, 1 };
            int count=0;             
            int n=3;
       
            for (int i = 3; ; i += 2)
            {
                var t = (trib[n-1]+trib[n-2]+trib[n-3])%i;

                while (t > 0&&n<100000)
                {
                    trib.Add(t);
                    n++;
                    t = (trib[n - 1] + trib[n - 2] + trib[n - 3]) % i;
                }

                trib = new List<long> { 1, 1, 1 };
                n = 3;
                if (t > 0)
                {
                    Console.WriteLine(i);
                    count++;
                    if (count == l) return i;
                }
            }
            
            
        }

Perl:

#!/usr/bin/perl

my $a = 1;
my $b = 1;
my $c = 1;

my $wc = 0;
for (my $k = 1; ; $k += 2) { 
  if (!modrun($k)) { 
    print $k, "\n";
    $wc++;
    last if ($wc == 124);
  }
}

sub modrun
{
  my ($mod) = shift;
  my %hit;

  my $a = 1;
  my $b = 1;
  my $c = 1;

  while (1) {
    #print "$a $b $c\n";
    return 0 if ($hit{"$a:$b:$c"} > 1);
    $hit{"$a:$b:$c"}++;

    my $t = ($a + $b + $c) % $mod;
    return 1 if ($t == 0);

    $a = $b;
    $b = $c;
    $c = $t;
  }
}

Pascal:

program bidon;
uses minimaple;

function tribo(n:longint):longint;
var a1,a2,a3,a4,i:longint;
begin
  a1:=1;
  a2:=1;
  a3:=1;
  for i:=1 to n*n do
  begin
    a4:=(a1+a2+a3) mod n;
    a1:=a2;
    a2:=a3;
    a3:=a4;
    if a3=0 then break;
  end;
  if i=n*n then i:=0;
  tribo:=i;
end;

function res(n:longint):longint;
var i,som:longint;
begin
  som:=0;
  i:=1;
  while som<>n do
  begin
    i:=i+2;
    if tribo(i)=0 then som:=som+1;
  end;
  res:=i;
end;

begin
  writeln(res(124));
end.

Basic:

n% = 1: k% = 0
DO
   a% = 1: b% = 1: c% = 1
   DO
      d% = a% + b% + c%
      a% = b% MOD n%
      b% = c% MOD n%
      c% = d% MOD n%
      IF a% = 1 AND b% = 1 AND c% = 1 THEN
         k% = k% + 1
         EXIT DO
      ELSEIF a% = 0 THEN
         EXIT DO
      END IF
   LOOP
   IF k% = 124 THEN
      PRINT n%
      EXIT DO
   END IF
   n% = n% + 2
LOOP

Matlab:

function pe_225

N=124;
k=1;
current=27;
while k<N
    current=current+2;
    if ~isdivisibleby(current)
        k=k+1;
        fprintf('\n%d. %d does not divide the series.',k,current);
    end;
end;

function c=isdivisibleby(n)
    T=cell(n);
    u=[1 1 1]';
    A=[1 1 1;1 0 0;0 1 0];
    while 1
        u=mod(A*u,n);
        if u(1)==0,
            c=1;
            break;
        elseif ~any(T{u(2),u(3)}==u(1))
                T{u(2),u(3)}=[T{u(2),u(3)} u(1)];
            else
                c=0;
                break;
        end;
    end;