login
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.
8
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.
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. A337476 (position of the first occurrence of each n), A337478.
Sequence in context: A249130 A134997 A355691 * A104605 A300953 A145740
KEYWORD
nonn
AUTHOR
Antti Karttunen, Aug 28 2020
STATUS
approved