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,11

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)

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.

Prog

(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))));

Crossrefs

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

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

Sequence in context: A249130 A134997 A355691 * A104605 A300953 A145740

Adjacent sequences: A337471 A337472 A337473 * A337475 A337476 A337477

Keyword

nonn

Author

Antti Karttunen, Aug 28 2020

Status

approved