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

3, 5, 7, 7, 11, 13, 13, 17, 19, 19, 23, 19, 21, 29, 31, 31, 31, 37, 37, 41, 43, 43, 47, 43, 43, 53, 43, 41, 59, 61, 61, 61, 67, 67, 71, 73, 73, 71, 79, 79, 83, 79, 79, 89, 79, 79, 79, 97, 97, 101, 103, 103, 107, 109, 109, 113, 109, 109, 113, 109

Offset: 1

Author

Moritz Firsching, Aug 04 2015

Keywords

• nonn

Comments

a(n) is prime for all n<=10^10 except a(13)=21.

a(n) <= 2n + 1.

a(n) = 2n + 1 if and only if 2n + 1 is prime.

a(n) = 2n - 1 if and only if 2n - 1 is a prime and 2n - 1 = 1 mod 6.

a(n) = 2n - 3 if and only if 2n - 3 is a prime and 2n - 3 = 1 mod 30.

Links

• Moritz Firsching, Table of n, a(n) for n = 1..9999

Crossrefs

Cf. A002476, A132230, A261301.

A186253(n) is a^n(2) where a^n denotes the n-th composition.

Programs

PARI

a(last_a) = {
  local(A=last_a,B=last_a,C=2*last_a+1);
  while(A>0,
    D=divisors(C);
    k1=10*D[2];
    for(j=2,matsize(D)[2],d=D[j];k=((A+1-B+d)/2)%d;
      if(k==0,k=d); if(k<=k1,k1=k;d1=d));
    if(k1-1+d1==A,B=B+1);
    A = max(A-(k1-1)-d1,0);
    B = B + k1;
    C = C - (d1 - 1);
  );
  return(B);
}
a(n)={
my(A=n, B=n, C=2*n+1);
while(A>0,
my(k1=oo,d1);
fordiv(C,d,
if(d==1,next);
my(k=((A+1-B+d)/2)%d);
if(k==0, k=d);
if(k<=k1, k1=k; d1=d)
);
A -= k1 - 1 + d1;
B += k1 + (A==0);
C -= d1 - 1;
);
B;
} \\ Charles R Greathouse IV, Nov 04 2015

Sage

def a(n):
    g=n
    n+=1
    while(g!=0):
        g=g-gcd(n,g)
        n+=1
    return n