cp's OEIS Frontend

A260940 a(n) is the smallest index j>n such that g(j)=0 for the sequence g defined (for indices > n) by g(n+1)=n and g(i) = g(i-1) - gcd(i,g(i-1)).

%I A260940 #22 Nov 04 2015 11:01:39
%S A260940 3,5,7,7,11,13,13,17,19,19,23,19,21,29,31,31,31,37,37,41,43,43,47,43,
%T A260940 43,53,43,41,59,61,61,61,67,67,71,73,73,71,79,79,83,79,79,89,79,79,79,
%U A260940 97,97,101,103,103,107,109,109,113,109,109,113,109
%N A260940 a(n) is the smallest index j>n such that g(j)=0 for the sequence g defined (for indices > n) by g(n+1)=n and g(i) = g(i-1) - gcd(i,g(i-1)).
%C A260940 a(n) is prime for all n<=10^10 except a(13)=21.
%C A260940 a(n) <= 2n + 1.
%C A260940 a(n) = 2n + 1 if and only if 2n + 1 is prime.
%C A260940 a(n) = 2n - 1 if and only if 2n - 1 is a prime and 2n - 1 = 1 mod 6.
%C A260940 a(n) = 2n - 3 if and only if 2n - 3 is a prime and 2n - 3 = 1 mod 30.
%H A260940 Moritz Firsching, <a href="/A260940/b260940.txt">Table of n, a(n) for n = 1..9999</a>
%o A260940 (Sage)
%o A260940 def a(n):
%o A260940     g=n
%o A260940     n+=1
%o A260940     while(g!=0):
%o A260940         g=g-gcd(n,g)
%o A260940         n+=1
%o A260940     return n
%o A260940 (PARI)
%o A260940 a(last_a) = {
%o A260940   local(A=last_a,B=last_a,C=2*last_a+1);
%o A260940   while(A>0,
%o A260940     D=divisors(C);
%o A260940     k1=10*D[2];
%o A260940     for(j=2,matsize(D)[2],d=D[j];k=((A+1-B+d)/2)%d;
%o A260940       if(k==0,k=d); if(k<=k1,k1=k;d1=d));
%o A260940     if(k1-1+d1==A,B=B+1);
%o A260940     A = max(A-(k1-1)-d1,0);
%o A260940     B = B + k1;
%o A260940     C = C - (d1 - 1);
%o A260940   );
%o A260940   return(B);
%o A260940 }
%o A260940 a(n)={
%o A260940 my(A=n, B=n, C=2*n+1);
%o A260940 while(A>0,
%o A260940 my(k1=oo,d1);
%o A260940 fordiv(C,d,
%o A260940 if(d==1,next);
%o A260940 my(k=((A+1-B+d)/2)%d);
%o A260940 if(k==0, k=d);
%o A260940 if(k<=k1, k1=k; d1=d)
%o A260940 );
%o A260940 A -= k1 - 1 + d1;
%o A260940 B += k1 + (A==0);
%o A260940 C -= d1 - 1;
%o A260940 );
%o A260940 B;
%o A260940 } \\ _Charles R Greathouse IV_, Nov 04 2015
%Y A260940 Cf. A002476, A132230, A261301.
%Y A260940 A186253(n) is a^n(2) where a^n denotes the n-th composition.
%K A260940 nonn
%O A260940 1,1
%A A260940 _Moritz Firsching_, Aug 04 2015