A171462 -id:A171462 - cp's OEIS frontend

A335905 Number of distinct integers encountered on all possible paths from n to any first encountered powers of 2 (that are excluded from the count), when using the transitions x -> x - (x/p) and x -> x + (x/p) in any order, where p is the largest prime dividing x.

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

Offset: 1

Antti Karttunen, Jun 30 2020

nonn

			From 9 one can reach with the transitions x -> A171462(x) (leftward arrow) and x -> A335876(x) (rightward arrow) the following three numbers, when one doesn't expand any power of 2 (in this case, 4, 8 and 16, that are not included in the count) further:
       9
      / \
     6   12
    / \ / \
  (4) (8) (16)
thus a(9) = 3.
From 10 one can reach with the transitions x -> A171462(x) and x -> A335876(x) the following two numbers (10 & 12), when one doesn't expand any powers of 2 (8 and 16 in this case, not counted) further:
  10
   |\
   | \
   | 12
   | /\
   |/  \
  (8)  (16)
thus a(10) = 2.
For n = 9, the numbers encountered are 6, 9, 12, thus a(9) = 3.
For n = 67, the numbers encountered are 48, 60, 66, 67, 68, 72, 96, thus a(67) = 7.
For n = 105, the numbers encountered are 48, 72, 90, 96, 105, 108, 120, 144, 192, thus a(105) = 9.

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A006530, A171462, A335876, A335906.

Cf. also A332809, A335884, A335885, A335904.

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));
A335905(n) = if(A209229(n),0,my(xs=Set([n]),allxs=xs,newxs,a,b,u); for(k=1,oo, newxs=Set([]); if(!#xs, return(#allxs)); allxs = setunion(allxs,xs); for(i=1,#xs,u = xs[i]; a = A171462(u); if(!A209229(a), newxs = setunion([a],newxs)); b = A335876(u); if(!A209229(b), newxs = setunion([b],newxs))); xs = newxs));

A335906 Number of distinct integers encountered on all possible paths from n to any first encountered powers of 2 (that are included in the count), when using the transitions x -> x - (x/p) and x -> x + (x/p) in any order, where p is the largest prime dividing x.

Original entry on oeis.org

1, 1, 3, 1, 4, 3, 4, 1, 6, 4, 5, 3, 5, 4, 7, 1, 7, 6, 8, 4, 7, 5, 6, 3, 9, 5, 10, 4, 9, 7, 8, 1, 8, 7, 9, 6, 9, 8, 8, 4, 9, 7, 10, 5, 11, 6, 7, 3, 9, 9, 11, 5, 13, 10, 10, 4, 12, 9, 10, 7, 9, 8, 11, 1, 10, 8, 10, 7, 9, 9, 10, 6, 10, 9, 13, 8, 11, 8, 10, 4, 15, 9, 10, 7, 13, 10, 13, 5, 14, 11, 10, 6, 12, 7, 15, 3, 10, 9, 12, 9, 15, 11, 14, 5, 13

Offset: 1

Antti Karttunen, Jun 30 2020

nonn

			From 9 one can reach with the transitions x -> A171462(x) (leftward arrow) and x -> A335876(x) (rightward arrow) the following six numbers, when one doesn't expand any power of 2 further:
       9
      / \
     6   12
    / \ / \
   4   8   16
thus a(9) = 6.
From 10 one can reach with the transitions x -> A171462(x) and x -> A335876(x) the following for numbers, when one doesn't expand any power of 2 further:
  10
   |\
   | \
   | 12
   | /\
   |/  \
   8   16
thus a(10) = 4.
From 15 one can reach with the transitions x -> A171462(x) and x -> A335876(x) the following seven numbers, when one doesn't expand any power of 2 further:
        15
       /  \
      /    \
    12<----18
    / \      \
   /   \      \
  8     16<----24
                \
                 \
                  32
thus a(15) = 7.

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A006530, A171462, A335876, A335905.

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));
A335906(n) = { my(xs=Set([n]),allxs=xs,newxs,a,b,u); for(k=1,oo, newxs=Set([]); if(!#xs, return(#allxs)); allxs = setunion(allxs,xs); for(i=1,#xs,u = xs[i]; if(!A209229(u), newxs = setunion([A171462(u)],newxs); newxs = setunion([A335876(u)],newxs))); xs = newxs); };

A351168 If n = p_1^e_1 * ... * p_k^e_k, where p_1 < ... < p_k are primes, then a(n) is obtained by replacing the last factor p_k^e_k by (p_k - 1)^e_k; a(1) = 1.

Original entry on oeis.org

1, 1, 2, 1, 4, 4, 6, 1, 4, 8, 10, 8, 12, 12, 12, 1, 16, 8, 18, 16, 18, 20, 22, 16, 16, 24, 8, 24, 28, 24, 30, 1, 30, 32, 30, 16, 36, 36, 36, 32, 40, 36, 42, 40, 36, 44, 46, 32, 36, 32, 48, 48, 52, 16, 50, 48, 54, 56, 58, 48, 60, 60, 54, 1, 60, 60, 66, 64, 66, 60, 70, 32, 72, 72, 48

Offset: 1

Ben Polson, Feb 03 2022

nonn

First time a term appears four or more times in a row is when n = 1684.

			The prime factorization of 44 is 2^2 * 11^1, so a(44) = 2^2 * 10^1 = 40.
The prime factorization of 50 is 2^1 * 5^2, so a(50) = 2^1 * 4^2 = 32.

Amiram Eldar, Table of n, a(n) for n = 1..10000
Jan Misali, What should we call the other bases?, Web page, no date. Inspiration for this sequence.

Cf. A006530 (greatest prime), A071178 (its exponent).

Cf. A171462 (one instance of the decrement), A003958 (all primes decremented), A351419, A351425.

a[n_] := Module[{f = FactorInteger[n]}, n*(1 - 1/f[[-1, 1]])^f[[-1, 2]]]; a[1] = 1; Array[a, 100] (* Amiram Eldar, Feb 04 2022 *)

a(n) = my(f=factor(n),r=matsize(f)[1]); if(r, f[r,1]--); factorback(f); \\ Kevin Ryde, Feb 03 2022

a(n) = n*(1 - 1/p_k)^e_k where prime factorization n = p_1^e_1 * ... * p_k^e_k with ascending p_1 < ... < p_k.

a(n) = n*(1 - 1/A006530(n))^A071178(n).

a(1) = 1 prepended by Michel Marcus, Feb 04 2022

Edited by N. J. A. Sloane, Feb 11 2022

A343555 a(n) = numerator(max_{k=2..n}(A191898(n, k)/k)), n>=2.

Original entry on oeis.org

-1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 8, 1, 1, 1, 1, 2, 4, 5, 1, 1, 1, 6, 1, 3, 1, 8, 1, 1, 20, 8, 24, 1, 1, 9, 8, 2, 1, 4, 1, 5, 8, 11, 1, 1, 1, 2, 32, 6, 1, 1, 8, 3, 12, 14, 1, 8, 1, 15, 4, 1, 48, 20, 1, 8, 44, 24, 1, 1, 1, 18, 8, 9, 60, 8

Offset: 2

Mats Granvik, Apr 19 2021

			max(-1/2) = -1/2 therefore a(2) = -1,
max(1/2, -2/3) = 1/2 therefore a(3) = 1,
max(-1/2, 1/3, -1/4) = 1/3 therefore a(4) = 1,
max(1/2, 1/3, 1/4, -4/5) = 1/2 therefore a(5) = 1
max(-1/2, -2/3, -1/4, 1/5, 1/3) = 1/3 therefore a(6) = 1,
max(1/2, 1/3, 1/4, 1/5, 1/6, -6/7) = 1/2 therefore a(7) = 1,
max(-1/2, 1/3, -1/4, 1/5, -1/6, 1/7, -1/8) = 1/3 therefore a(8) = 1,
max(1/2, -2/3, 1/4, 1/5, -1/3, 1/7, 1/8, -2/9) = 1/2 therefore a(9) = 1,
max(-1/2, 1/3, -1/4, -4/5, -1/6, 1/7, -1/8, 1/9, 2/5) = 2/5 therefore a(10) = 2.

Antti Karttunen, Table of n, a(n) for n = 2..20000

Cf. A343556 (denominator). Cf. A171462, A191898.

a[n_] := DivisorSum[n, MoebiusMu[#] # &]; nn = 78; Numerator[
Table[Max[Table[a[GCD[n, k]]/k, {k, 2, n}]], {n, 2, nn}]]

memoA191898 = Map();
A191898sq(n, k) = if(n<1 || k<1, 0, n==1 || k==1, 1, k>n, A191898sq(k, n), kA191898sq(k, (n-1)%k+1), my(v); if(mapisdefined(memoA191898,[n,k],&v), v, v = -sum( i=1, n-1, A191898sq(n, i)); mapput(memoA191898,[n,k],v); (v))); \\ After Michael Somos' code in A191898
A343555(n) = { my(m=0,r); for(k=2, n, r = A191898sq(n, k)/k; if(!m || (r > m), m = r)); numerator(m); }; \\ Antti Karttunen, Jan 28 2025

n>=2: a(n) = numerator(max_{k=2..n}(A191898(n, k)/k)).

A343556 a(n) = denominator(max_{k=2..n}(A191898(n, k)/k)), n>=2.

Original entry on oeis.org

2, 2, 3, 2, 3, 2, 3, 2, 5, 2, 3, 2, 7, 15, 3, 2, 3, 2, 5, 7, 11, 2, 3, 2, 13, 2, 7, 2, 15, 2, 3, 33, 17, 35, 3, 2, 19, 13, 5, 2, 7, 2, 11, 15, 23, 2, 3, 2, 5, 51, 13, 2, 3, 11, 7, 19, 29, 2, 15, 2, 31, 7, 3, 65, 33, 2, 17, 69, 35, 2, 3, 2, 37, 15, 19, 77, 13

Offset: 2

Mats Granvik, Apr 19 2021

			max(-1/2) = -1/2 therefore a(2) = 2,
max(1/2, -2/3) = 1/2 therefore a(3) = 2,
max(-1/2, 1/3, -1/4) = 1/3 therefore a(4) = 3,
max(1/2, 1/3, 1/4, -4/5) = 1/2 therefore a(5) = 2
max(-1/2, -2/3, -1/4, 1/5, 1/3) = 1/3 therefore a(6) = 3,
max(1/2, 1/3, 1/4, 1/5, 1/6, -6/7) = 1/2 therefore a(7) = 2,
max(-1/2, 1/3, -1/4, 1/5, -1/6, 1/7, -1/8) = 1/3 therefore a(8) = 3,
max(1/2, -2/3, 1/4, 1/5, -1/3, 1/7, 1/8, -2/9) = 1/2 therefore a(9) = 2,
max(-1/2, 1/3, -1/4, -4/5, -1/6, 1/7, -1/8, 1/9, 2/5) = 2/5 therefore a(10) = 5.

Antti Karttunen, Table of n, a(n) for n = 2..20000

Cf. A343555 (numerators). Cf. A171462, A191898.

a[n_] := DivisorSum[n, MoebiusMu[#] # &]; nn = 78; Denominator[Table[Max[Table[a[GCD[n, k]]/k, {k, 2, n}]], {n, 2, nn}]]

memoA191898 = Map();
A191898sq(n, k) = if(n<1 || k<1, 0, n==1 || k==1, 1, k>n, A191898sq(k, n), kA191898sq(k, (n-1)%k+1), my(v); if(mapisdefined(memoA191898,[n,k],&v), v, v = -sum( i=1, n-1, A191898sq(n, i)); mapput(memoA191898,[n,k],v); (v))); \\ After Michael Somos' code in A191898
A343556(n) = { my(m=0,r); for(k=2, n, r = A191898sq(n, k)/k; if(!m || (r > m), m = r)); denominator(m); }; \\ Antti Karttunen, Jan 28 2025

n>=2: a(n) = denominator(max_{k=2..n}(A191898(n, k)/k)).

cp's OEIS Frontend

A335905 Number of distinct integers encountered on all possible paths from n to any first encountered powers of 2 (that are excluded from the count), when using the transitions x -> x - (x/p) and x -> x + (x/p) in any order, where p is the largest prime dividing x.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

A335906 Number of distinct integers encountered on all possible paths from n to any first encountered powers of 2 (that are included in the count), when using the transitions x -> x - (x/p) and x -> x + (x/p) in any order, where p is the largest prime dividing x.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

A351168 If n = p_1^e_1 * ... * p_k^e_k, where p_1 < ... < p_k are primes, then a(n) is obtained by replacing the last factor p_k^e_k by (p_k - 1)^e_k; a(1) = 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A343555 a(n) = numerator(max_{k=2..n}(A191898(n, k)/k)), n>=2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A343556 a(n) = denominator(max_{k=2..n}(A191898(n, k)/k)), n>=2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula