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.

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

Jianing Song, Table of n, a(n) for n = 0..10000

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

Cf. A006530 (gpf), A076563, A309892, A356429.

Sequence in context: A355915 A357900 A357732 * A158819 A031279 A124778

Adjacent sequences: A356425 A356426 A356427 * A356429 A356430 A356431

Keyword

nonn

Author

_Jianing Song_, Aug 07 2022

Status

approved