A076563 -id:A076563 - cp's OEIS frontend

A309892 a(0) = 0, a(1) = 1, and for any n > 1, a(n) is the number of iterations of the map x -> x - gpf(x) (where gpf(x) denotes the greatest prime factor of x) required to reach 0 starting from n.

0, 1, 1, 1, 2, 1, 2, 1, 3, 3, 2, 1, 4, 1, 2, 3, 3, 1, 4, 1, 4, 3, 2, 1, 4, 5, 2, 5, 4, 1, 6, 1, 7, 3, 2, 5, 4, 1, 2, 3, 6, 1, 6, 1, 4, 7, 2, 1, 8, 7, 8, 3, 4, 1, 4, 5, 8, 3, 2, 1, 6, 1, 2, 9, 3, 5, 6, 1, 4, 3, 10, 1, 4, 1, 2, 11, 4, 7, 6, 1, 12, 7, 2, 1, 8, 5

Offset: 0

Rémy Sigrist, Aug 21 2019

nonn

This sequence is similar to A175126: here we subtract the greatest prime factor, there the least prime factor.

			For n = 16:
- the greatest prime factor of 16 is 2,
- the greatest prime factor of 16-2 = 14 is 7,
- the greatest prime factor of 14-7 = 7 is 7,
- 7 - 7 = 0,
- hence a(16) = 3.

Antti Karttunen, Table of n, a(n) for n = 0..16384
Antti Karttunen, Data supplement: n, a(n) computed for n = 0..65537

Cf. A006530, A052126, A076563, A175126.

a(n) = for (k=0, oo, if (n==0, return (k), n==1, n--, my (f=factor(n)); n-=f[#f~,1]))

a(n) <= n / A006530(n) for any n > 0.

a(n) = n if n <= 1, for n >= 2, a(n) = 1+a(A076563(n)). - Antti Karttunen, Aug 22 2019

A354512 Number of solutions m >= 2 to m - gpf(m) = n, gpf = A006530.

Original entry on oeis.org

0, 1, 1, 0, 1, 2, 1, 0, 1, 1, 1, 0, 1, 2, 2, 0, 1, 0, 1, 1, 2, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 2, 1, 2, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 0, 1, 0, 2, 1, 1, 0, 2, 1, 1, 1, 1, 0, 1, 2, 1, 0, 1, 1, 1, 1, 2, 1, 1, 0, 1, 1, 1, 1, 2, 2, 1, 0, 0, 1, 1, 0, 2, 1, 1, 1, 1, 0, 2

Offset: 1

Jianing Song, Aug 16 2022

Number of primes p such that gpf(n+p) = p (such p must be prime factors of n).
Number of distinct prime factors p of n such that n+p is p-smooth.
Clearly we have a(n) <= omega(n) for all n, omega = A001221. The differences are given by A354527.
Is this sequence unbounded? Note that 4 does not appear until a(1660577).

			a(78) = 2 since the prime factors of 78 are 2,3,13, and we have gpf(78+3) = 3 and gpf(78+13) = 13, so the solutions to m - gpf(m) = 78 are m = 78+3 = 81 or m = 78+13 = 91. Note that gpf(78+2) != 2.
a(12) = 0 since the prime factors of 12 are 2,3, and we have gpf(12+2) != 2 and gpf(12+3) != 3.

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

Cf. A006530, A076563, A001221, A354516 (indices of first occurrence of each number), A354527.

Cf. A354514 (0 together with indices of positive terms), A354515 (indices of 0), A354516, A354525 (indices n for which a(n) reaches omega(n)), A354526 (indices n for which a(n) is smaller than omega(n)).

gpf(n) = vecmax(factor(n)[, 1]);
a(n) = my(f=factor(n)[, 1]); sum(i=1, #f, gpf(n+f[i])==f[i])

A354514 Numbers k such that m - gpf(m) = k has solutions m >= 2, gpf = A006530.

Original entry on oeis.org

0, 2, 3, 5, 6, 7, 9, 10, 11, 13, 14, 15, 17, 19, 20, 21, 22, 23, 24, 25, 26, 28, 29, 30, 31, 33, 34, 35, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 49, 51, 52, 53, 55, 56, 57, 58, 59, 61, 62, 63, 65, 66, 67, 68, 69, 70, 71, 73, 74, 75, 76, 77, 78, 79, 82, 83, 85, 86, 87, 88

Offset: 1

Jianing Song, Aug 16 2022

Numbers k such that there is a prime p such that gpf(k+p) = p (such p must be a prime factor of n).
Numbers k such that there is a prime factor p of k such that k+p is p-smooth.
A076563 sorted and duplicates removed.

			0 is a term because 0 = p - gpf(p) for every prime p.
if k/gpf(k) <= nextprime(gpf(k)) - 2, where nextprime = A151800, then k is a term since k+gpf(k) <= gpf(k)*(nextprime(gpf(k)) - 1) implies gpf(k+gpf(k)) = gpf(k).

Jianing Song, Table of n, a(n) for n = 1..8650 (all terms <= 10000)

Cf. A006530, A076563, A151800.

0 together with indices of positive terms in A354512. Complement of A354515.

gpf(n) = vecmax(factor(n)[, 1]);
isA354514(n) = if(n, my(f=factor(n)[, 1]); for(i=1, #f, if(gpf(n+f[i])==f[i], return(1))); 0, 1)

A354515 Numbers k such that m - gpf(m) = k has no solution m >= 2, gpf = A006530.

Original entry on oeis.org

1, 4, 8, 12, 16, 18, 27, 32, 36, 48, 50, 54, 60, 64, 72, 80, 81, 84, 90, 96, 100, 108, 112, 125, 128, 132, 135, 144, 147, 150, 160, 162, 176, 180, 192, 196, 198, 200, 208, 210, 216, 224, 225, 234, 242, 243, 250, 252, 256, 270, 275, 280, 288, 294, 300, 306, 320, 324

Offset: 1

Jianing Song, Aug 16 2022

Numbers k such that there is no prime p such that gpf(k+p) = p.

Numbers k such that there is no prime factor p of k such that k+p is p-smooth.

			12 is a term since the prime factors of 12 are 2,3, and we have gpf(12+2) != 2 and gpf(12+3) != 3.

Jianing Song, Table of n, a(n) for n = 1..9826 (all terms <= 80000)

Cf. A006530, A076563.

Indices of 0 in A354512. Complement of A354514.

gpf(n) = vecmax(factor(n)[, 1]);
isA354515(n) = if(n, my(f=factor(n)[, 1]); for(i=1, #f, if(gpf(n+f[i])==f[i], return(0))); 1, 0)

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.

Original entry on oeis.org

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

Jianing Song, Aug 07 2022

nonn

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

			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

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

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

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)

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

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

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).

A356438 Numbers k such that A309892(k) = k/gpf(k), where gpf = A006530.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, 19, 20, 21, 22, 23, 25, 26, 28, 29, 30, 31, 33, 34, 35, 37, 38, 39, 41, 42, 43, 44, 46, 47, 49, 51, 52, 53, 55, 56, 57, 58, 59, 61, 62, 63, 65, 66, 67, 68, 69, 70, 71, 73, 74, 76, 77, 78, 79, 82, 83, 85

Offset: 1

Jianing Song, Aug 07 2022

Note that A309892(k) <= k/gpf(k); these sequence lists k such that the equality holds.

For k >= 2, k is a term if and only if k/gpf(k) < nextprime(gpf(k)), where nextprime = A151800.

			15 is a term since the number of steps needed to reach 0 of the iteration x -> x - gpf(x) starting at 15 is 3: 15 -> 10 -> 5 -> 0, and 3 = 15/gpf(15).

Jianing Song, Table of n, a(n) for n = 1..36902 (all terms <= 50000)

Other than 1, indices of 1 in A356428.
Includes A000040 and A001358 as subsequences.
Complement of A356441.
Cf. A309892, A006530 (gpf), A151800, A076563.

isA356438(n) = if(n>1, my(p=vecmax(factor(n)[, 1])); n/p

A356441 Numbers k such that A309892(k) < k/gpf(k), where gpf = A006530; complement of A356438.

Original entry on oeis.org

8, 16, 18, 24, 27, 32, 36, 40, 45, 48, 50, 54, 60, 64, 72, 75, 80, 81, 84, 90, 96, 98, 100, 105, 108, 112, 120, 125, 126, 128, 135, 140, 144, 147, 150, 154, 160, 162, 165, 168, 175, 176, 180, 189, 192, 196, 198, 200, 210, 216, 220, 224, 225, 231, 234, 240, 242, 243

Offset: 1

Jianing Song, Aug 07 2022

k is a term if and only if k/gpf(k) > nextprime(gpf(k)), where nextprime = A151800.

			8 is a term since the number of steps needed to reach 0 of the iteration x -> x - gpf(x) starting at 8 is 3: 8 -> 6 -> 3 -> 0, and 3 < 8/gpf(8).

Jianing Song, Table of n, a(n) for n = 1..13098 (all terms <= 50000)

Cf. A356438, A309892, A006530 (gpf), A151800, A076563.

isA356441(n) = if(n>1, my(p=vecmax(factor(n)[, 1])); n/p>nextprime(p+1), 0)

A342609 Positive integers that cannot be written in the form k - gpf(k) +- 1 for some integer k, where gpf(k) is the greatest prime factor of k.

Original entry on oeis.org

17, 49, 161, 197, 199, 209, 251, 391, 419, 449, 649, 685, 769, 799, 883, 967, 1057, 1189, 1249, 1301, 1457, 1481, 1681, 1793, 1937, 1979, 2001, 2029, 2089, 2177, 2209, 2311, 2377, 2379, 2419, 2431, 2449, 2549, 2551, 2575, 2591, 2705, 2729, 2899, 3041, 3073

Offset: 1

Christian Bagshaw, Mar 16 2021

nonn

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A006530, A076563.

f:= proc(n) local g;
  g:= max(numtheory:-factorset(n));
  n-g+1,n-g-1
end proc:
sort(convert({$1..5000} minus map(f, {$1..10001}),list)); # Robert Israel, Apr 12 2021

A354516 Smallest k such that m - gpf(m) = k has exactly n solutions m >= 2, gpf = A006530; or -1 if no such k exists.

Original entry on oeis.org

1, 2, 6, 483, 1660577

Offset: 0

Jianing Song, Aug 16 2022

Smallest k such that there are exactly n primes p such that gpf(k+p) = p (such p must be prime factors of k).
Smallest k having exactly n distinct prime factors p such that k+p is p-smooth.
Conjectures (if no term equals -1): (Start)
(1) Sequence is strictly increasing.
(2) All terms are squarefree.
(3) All terms are in A354525. (End)

			a(4) = 1660577: 1660577 = 17*23*31*127, and we have 1660577+17 = 2*13^2*17^3 is 17-smooth, 1660577+23 = 2^3*5^2*19^2*23 is 23-smooth, 1660577+31 = 2^6*3^3*31^2 is 31-smooth, 1660577+137 = 2*11*19*29*137, so m - gpf(m) = 1660577 has 4 solutions m = 1660577+17 = 1660594, 1660577+23 = 1660600, 1660577+31 = 1660608, and 1660577+137 = 1660714.

Cf. A006530, A076563, A354512, A354525.

gpf(n) = vecmax(factor(n)[, 1]);
A354512(n) = my(f=factor(n)[, 1]); sum(i=1, #f, gpf(n+f[i])==f[i]);
a(n) = my(k=1); while(omega(k)A354512(k) != n, k++); return(k)

A356427 a(0) = 0, a(1) = 1; for n > 1, a(n) is the last step before reaching 0 of the iterations x -> x - gpf(x) starting at n, where gpf = A006530.

Original entry on oeis.org

0, 1, 2, 3, 2, 5, 3, 7, 3, 3, 5, 11, 3, 13, 7, 5, 7, 17, 5, 19, 5, 7, 11, 23, 7, 5, 13, 7, 7, 29, 5, 31, 5, 11, 17, 7, 11, 37, 19, 13, 7, 41, 7, 43, 11, 7, 23, 47, 7, 7, 7, 17, 13, 53, 17, 11, 7, 19, 29, 59, 11, 61, 31, 7, 31, 13, 11, 67, 17, 23, 7, 71, 23, 73, 37, 7, 19, 11

Offset: 0

Jianing Song, Aug 07 2022

nonn

For n > 1, a(n) is the unique prime in the iterations x -> x - gpf(x) starting at n and ending at 0.

			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, so a(48) = 7.
96 (3) -> 93 (31) -> 62 (31) -> 31 (31) -> 0, so a(96) = 31.

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

Cf. A006530 (gpf), A076563, A309892, A356438, A356441.

a(n) = if(n>1, my(s=n); while(!isprime(s), s=s-vecmax(factor(s)[, 1])); s, n)

For n > 0, a(n) = gpf(n) if n is in A356438; otherwise a(n) > gpf(n).

cp's OEIS Frontend

A309892 a(0) = 0, a(1) = 1, and for any n > 1, a(n) is the number of iterations of the map x -> x - gpf(x) (where gpf(x) denotes the greatest prime factor of x) required to reach 0 starting from n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A354512 Number of solutions m >= 2 to m - gpf(m) = n, gpf = A006530.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A354514 Numbers k such that m - gpf(m) = k has solutions m >= 2, gpf = A006530.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A354515 Numbers k such that m - gpf(m) = k has no solution m >= 2, gpf = A006530.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

Python

Formula

A356438 Numbers k such that A309892(k) = k/gpf(k), where gpf = A006530.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A356441 Numbers k such that A309892(k) < k/gpf(k), where gpf = A006530; complement of A356438.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A342609 Positive integers that cannot be written in the form k - gpf(k) +- 1 for some integer k, where gpf(k) is the greatest prime factor of k.

Views

Author

Keywords

Links