|
|
A335885
|
|
The length of a shortest path from n to a power of 2, when applying the nondeterministic maps k -> k - k/p and k -> k + k/p, where p can be any of the odd prime factors of k, and the maps can be applied in any order.
|
|
15
|
|
|
0, 0, 1, 0, 1, 1, 1, 0, 2, 1, 2, 1, 2, 1, 2, 0, 1, 2, 2, 1, 2, 2, 2, 1, 2, 2, 3, 1, 2, 2, 1, 0, 3, 1, 2, 2, 3, 2, 3, 1, 2, 2, 3, 2, 3, 2, 2, 1, 2, 2, 2, 2, 3, 3, 3, 1, 3, 2, 3, 2, 2, 1, 3, 0, 3, 3, 2, 1, 3, 2, 3, 2, 3, 3, 3, 2, 3, 3, 2, 1, 4, 2, 3, 2, 2, 3, 3, 2, 3, 3, 3, 2, 2, 2, 3, 1, 2, 2, 4, 2, 3, 2, 3, 2, 3
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,9
|
|
COMMENTS
|
The length of a shortest path from n to a power of 2, when using the transitions x -> A171462(x) and x -> A335876(x) in any order.
a((2^e)-1) is equal to A046051(e) = A001222((2^e)-1) when e is either a Mersenne exponent (in A000043), or some other number: 1, 4, 6, 8, 16, 32. For example, 32 is present because 2^32 - 1 = 4294967295 = 3*5*17*257*65537, a squarefree product of five known Fermat primes. - Antti Karttunen, Aug 11 2020
|
|
LINKS
|
|
|
FORMULA
|
Fully additive with a(2) = 0, and a(p) = 1+min(a(p-1), a(p+1)), for odd primes p.
For all n >= 0, a(A000244(n)) = n, and these also seem to give records.
|
|
EXAMPLE
|
A335876(67) = 68, and A171462(68) = 64 = 2^6, and this is the shortest path from 67 to a power of 2, thus a(67) = 2.
A171462(15749) = 15748, A335876(15748) = 15872, A335876(15872) = 16384 = 2^14, and this is the shortest path from 15749 to a power of 2, thus a(15749) = 3.
|
|
PROG
|
(PARI) A335885(n) = { my(f=factor(n)); sum(k=1, #f~, if(2==f[k, 1], 0, f[k, 2]*(1+min(A335885(f[k, 1]-1), A335885(f[k, 1]+1))))); };
(PARI)
\\ Or empirically as:
A171462(n) = if(1==n, 0, (n-(n/vecmax(factor(n)[, 1]))));
A335876(n) = if(1==n, 2, (n+(n/vecmax(factor(n)[, 1]))));
A209229(n) = (n && !bitand(n, n-1));
A335885(n) = if(A209229(n), 0, my(xs=Set([n]), newxs, a, b, u); for(k=1, oo, newxs=Set([]); for(i=1, #xs, u = xs[i]; a = A171462(u); if(A209229(a), return(k)); b = A335876(u); if(A209229(b), return(k)); newxs = setunion([a], newxs); newxs = setunion([b], newxs)); xs = newxs));
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|