A328324 An upper bound sequence for A327969, using the primorial number A002110(37) as a cut point limit when pruning A276086-branches from the search tree.

0, 1, 2, 2, 5, 2, 3, 2, 6, 4, 3, 2, 5, 2, 5, 6, 6, 2, 5, 2, 7, 4, 3, 2, 11, 4, 7, 22, 6, 2, 3, 2, 5, 4, 3, 5, 6, 2, 4, 4, 5, 2, 3, 2, 10, 5, 5, 2, 9, 6, 6, 8, 17, 2, 11, 7, 16, 4, 3, 2, 7, 2, 5, 9, 7, 5, 3, 2, 5, 8, 3, 2, 7, 2, 5, 8, 5, 6, 3, 2, 18, 10, 3, 2, 9, 4, 6, 6, 21, 2, 9, 6, 15, 4, 7, 12, 14, 2, 6, 9, 21, 2, 7, 2, 6, 3

Offset: 0

Author

Antti Karttunen, Oct 14 2019

Keywords

• nonn

Comments

If in the search tree (whose root is n) where the transitions x -> A003415(x) and x -> A276086(x) expand the tree at every point to two branches, the latter transition yields a number larger than A002110(37), that number (and the whole subtree whose root it is) will then be pruned from the tree, which entails that the procedure could miss shorter paths to zero than what it will find later from the other branches of the tree. Thus for all n, this sequence gives the guaranteed upper bound for the terms of A327969.

Note that A002110(37) = 35375166993717494840635767087951744212057570647889977422429870 is a 205-bit integer.

Crossrefs

Cf. A002110, A003415, A276086, A327969.

Programs

PARI

A003415(n) = if(n<=1, 0, my(f=factor(n)); n*sum(i=1, #f~, f[i, 2]/f[i, 1]));
A276086(n) = { my(m=1, p=2); while(n, m *= (p^(n%p)); n = n\p; p = nextprime(1+p)); (m); };
A327969(n,searchlim=0) = if(!n,n,my(xs=Set([n]),newxs,a,b,u); for(k=1,oo, newxs=Set([]); for(i=1,#xs,u = xs[i]; a = A003415(u); if(0==a, return(k)); if(isprime(a), return(k+2)); b = A276086(u); if(isprime(b), return(k+1+(u>2))); newxs = setunion([a],newxs); if(!searchlim || (b<=searchlim),newxs = setunion([b],newxs))); xs = newxs));
A002110(n) = prod(i=1,n,prime(i));
A328324(n) = A327969(n,A002110(37));

Formula

a(n) >= A327969(n) for all n.