login
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.
3
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,3
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.
FORMULA
a(n) >= A327969(n) for all n.
PROG
(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));
CROSSREFS
KEYWORD
nonn
AUTHOR
Antti Karttunen, Oct 14 2019
STATUS
approved