login
A356428
a(0) = a(1) = 0; for n > 1, a(n) is the number of distinct gpf(x)'s in the iterations x -> x - gpf(x) starting at n and ending at 0, where gpf = A006530.
3
0, 0, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 3, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 2, 2, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1
OFFSET
0,9
COMMENTS
Conjecture: sequence is unbounded. Since a(n) - a(n-gpf(n)) = 0 or 1 (see the formula below), this would imply that every number occurs in this sequence. But it seems that the bigger terms appear rather late: 6 does not appear until a(6664), and 7 does not appear until a(135450) (see A356429).
The last largest prime p in this iteration is found when p^2 > x in this iteration. - David A. Corneth, Aug 09 2022
LINKS
FORMULA
For n > 1, let p = gpf(n), then a(n) = 1+a(n-p) if p = n or gpf(n-p) > p; otherwise a(n) = a(n-p).
EXAMPLE
In the following examples the numbers produced by the iterations are listed together with their GPFs.
48 (3) -> 45 (5) -> 40 (5) -> 35 (7) -> ... -> 7 (7) -> 0, the distinct gpf(x)'s are 3, 5, and 7, so a(48) = 3.
96 (3) -> 93 (31) -> 62 (31) -> 31 (31) -> 0, the distinct gpf(x)'s are 3 and 31, so a(96) = 2.
320 (5) -> 315 (7) -> 308 (11) -> 297 (11) -> 286 (13) -> 273 (13) -> 260 (13) -> 247 (19) -> ... -> 19 (19) -> 0, the distinct gpf(x)'s are 5, 7, 11, 13, and 19, so a(320) = 5.
In the above computation for a(320) the calculation can stop at 247 (19) as all largest prime factors in positive x are 19. - David A. Corneth, Aug 09 2022
PROG
(PARI) gpf(n) = vecmax(factor(n)[, 1]);
a(n) = if(n>1, my(s=n, k=0, p); while(s, p=gpf(s); s-=p; k+=(s==0)||(gpf(s)>p)); k, 0)
(PARI) a(n) = {if(n <= 1, return(0)); my(cn = n, maxpr, pr = List()); while(cn > 1, maxpr = h(cn); listput(pr, maxpr); cn-=maxpr; if(maxpr^2 > cn, return(#Set(pr)))); #Set(pr)}
h(n) = {my(f = factor(n)); f[#f~, 1]} \\ David A. Corneth, Aug 08 2022
(Python)
from sympy import factorint
def gpf(n): return 1 if n == 1 else max(factorint(n))
def a(n):
s = set()
while n != 0: g = gpf(n); s.add(g); n = n - g
return len(s - {1})
print([a(n) for n in range(92)]) # Michael S. Branicky, Aug 08 2022
CROSSREFS
Sequence in context: A355915 A357900 A357732 * A158819 A031279 A124778
KEYWORD
nonn
AUTHOR
Jianing Song, Aug 07 2022
STATUS
approved