cp's OEIS Frontend

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.

%I A337474 #19 Sep 01 2020 08:53:52
%S A337474 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 A337474 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 A337474 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 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.
%C A337474 a(n) is the least k for which A337473(k, n) = 1.
%H A337474 Antti Karttunen, <a href="/A337474/b337474.txt">Table of n, a(n) for n = 1..65537</a>
%H A337474 <a href="/index/Pri#prime_indices">Index entries for sequences computed from indices in prime factorization</a>
%H A337474 <a href="/index/Pri#primorial_numbers">Index entries for sequences related to primorial numbers</a>
%H A337474 <a href="/index/Si#SIGMAN">Index entries for sequences related to sigma(n)</a>
%F A337474 a(n) = A336835(A108951(n)).
%F A337474 a(A181815(n)) = A337475(n).
%F A337474 For all n >= 0, a(A337476(n)) = n.
%F A337474 For all n >= 0, a(A337478(n)) >= n.
%o A337474 (PARI)
%o A337474 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 A337474(n) = for(i=0,oo,if(1==A337473sq(i,n),return(i)));
%o A337474 (PARI)
%o A337474 \\ This version uses binary search, which is faster in certain cases:
%o A337474 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 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 A337474 Cf. A003961, A108951, A181815, A336835, A337473, A337475.
%Y A337474 Cf. A337476 (position of the first occurrence of each n), A337478.
%K A337474 nonn
%O A337474 1,11
%A A337474 _Antti Karttunen_, Aug 28 2020