login
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

%I #19 Sep 01 2020 08:53:52

%S 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,

%T 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,

%U 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

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

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

%H Antti Karttunen, <a href="/A337474/b337474.txt">Table of n, a(n) for n = 1..65537</a>

%H <a href="/index/Pri#prime_indices">Index entries for sequences computed from indices in prime factorization</a>

%H <a href="/index/Pri#primorial_numbers">Index entries for sequences related to primorial numbers</a>

%H <a href="/index/Si#SIGMAN">Index entries for sequences related to sigma(n)</a>

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

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

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

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

%o (PARI)

%o 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));

%o A337474(n) = for(i=0,oo,if(1==A337473sq(i,n),return(i)));

%o (PARI)

%o \\ This version uses binary search, which is faster in certain cases:

%o 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));

%o 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))));

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

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

%K nonn

%O 1,11

%A _Antti Karttunen_, Aug 28 2020