A337474 Number of prime shifts (x -> A003961(x)) needed before the result is deficient, when starting from x = A108951(n), the primorial inflation of n.

0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 2, 1, 2, 2, 2, 0, 2, 1, 2, 2, 2, 2, 3, 1, 2, 2, 1, 2, 3, 2, 3, 0, 2, 2, 2, 1, 3, 3, 2, 2, 3, 2, 3, 2, 2, 3, 3, 1, 2, 2, 2, 2, 3, 1, 2, 2, 3, 3, 3, 2, 4, 3, 2, 0, 2, 2, 4, 2, 3, 2, 4, 1, 4, 3, 2, 3, 2, 2, 4, 2, 1, 3, 4, 2, 2, 3, 3, 2, 4, 2, 2, 3, 3, 3, 3, 1, 4, 2, 2, 2, 4, 2, 4, 2, 2

Offset: 1

Author

Antti Karttunen, Aug 28 2020

Keywords

• nonn

Comments

a(n) is the least k for which A337473(k, n) = 1.

Links

• Antti Karttunen, Table of n, a(n) for n = 1..65537
• Index entries for sequences computed from indices in prime factorization
• Index entries for sequences related to primorial numbers
• Index entries for sequences related to sigma(n)

Crossrefs

Cf. A003961, A108951, A181815, A336835, A337473, A337475.

Cf. A337476 (position of the first occurrence of each n), A337478.

Programs

PARI

A337473sq(n, k) = if(1==k,k, my(f=factor(k), h = #f~, prevpid=primepi(f[h,1]), e=f[h,2], p, s=1); forstep(i=h-1,0,-1, if(!i,pid=0,pid=primepi(f[i,1])); forstep(j=prevpid,(1+pid),-1, p=prime(j+n); s *= ((p^(1+e)-1)/((p-1)*(p^e)))); if(!pid,return(floor(s))); prevpid = pid; e += f[i,2]); floor(s));
A337474(n) = for(i=0,oo,if(1==A337473sq(i,n),return(i)));

PARI

\\ This version uses binary search, which is faster in certain cases:
isA337473sq1(n, k) = if(1==k,k, my(f=factor(k), h = #f~, prevpid=primepi(f[h,1]), e=f[h,2], p, s=1); forstep(i=h-1,0,-1, if(!i,pid=0,pid=primepi(f[i,1])); forstep(j=prevpid,(1+pid),-1, p=prime(j+n); s *= ((p^(1+e)-1)/((p-1)*(p^e)))); if(!pid,return(s<2)); prevpid = pid; e += f[i,2]); (s<2));
A337474(n) = if(!bitand(n,n-1),0,my(imin=0,imax=n,imid); for(i=0,oo, imid=(imax+imin)\2; if(1!=isA337473sq1(imid,n), imin = imid+1, if(1!=isA337473sq1(imid-1,n),return(imid), imax = imid-1))));

Formula

a(n) = A336835(A108951(n)).

a(A181815(n)) = A337475(n).

For all n >= 0, a(A337476(n)) = n.

For all n >= 0, a(A337478(n)) >= n.