A227944 -id:A227944 - cp's OEIS frontend

A227946 Smallest m such that the number of iterations of "take odd part of phi" to reach 1 from m (A227944) is n.

1, 2, 7, 19, 47, 163, 487, 1307, 2879, 19683, 39367, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 86093443, 258280327, 688747547, 3486784401, 10460353203

Offset: 0

Max Alekseyev, Oct 03 2013

The odd part of a number is its largest odd divisor (A000265), phi is Euler's totient function (A000010). - Alonso del Arte, Oct 13 2013

			a(1) = 2 because just one step is needed to reach 1 from 2, since phi(2) = 1. The numbers 3, 4, 5 and 6 also take one step.
a(2) = 7 because two steps are needed to reach 1 from 7: phi(7) = 6, the odd part of which is 3, and phi(3) = 2, the odd part of which is 1. The numbers from 8 to 18 take one or two steps to reach 1.
a(3) = 19 because three steps are needed to reach 1 from 19: phi(19) = 18, the odd part of which is 9, and phi(9) = 6, the odd part of which is 3, and phi(3) = 2, the odd part of which is 1.

A variant of A049117. - R. J. Mathar, Oct 06 2013

Cf. A007755, A053575, A000010.

import Data.List (elemIndex); import Data.Maybe (fromJust)
a227946 = (+ 1) . fromJust . (`elemIndex` a227944_list)
-- Reinhard Zumkeller, Nov 10 2013

a(n) = smallest m such that A227944(m)=n.

a(15) through a(21) copied over from A049117 by Max Alekseyev, Oct 13 2013

A053575 Odd part of phi(n): a(n) = A000265(A000010(n)).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 3, 1, 3, 1, 5, 1, 3, 3, 1, 1, 1, 3, 9, 1, 3, 5, 11, 1, 5, 3, 9, 3, 7, 1, 15, 1, 5, 1, 3, 3, 9, 9, 3, 1, 5, 3, 21, 5, 3, 11, 23, 1, 21, 5, 1, 3, 13, 9, 5, 3, 9, 7, 29, 1, 15, 15, 9, 1, 3, 5, 33, 1, 11, 3, 35, 3, 9, 9, 5, 9, 15, 3, 39, 1, 27, 5, 41, 3, 1, 21, 7, 5, 11, 3, 9, 11, 15, 23

Offset: 1

Labos Elemer, Jan 18 2000

This is not necessarily the squarefree kernel. E.g., for n=19, phi(19)=18 is divisible by 9, an odd square. Values at which this kernel is 1 correspond to A003401 (polygons constructible with ruler and compass).

Multiplicative with a(2^e) = 1, a(p^e) = p^(e-1)*A000265(p-1). - Christian G. Bower, May 16 2005

			n = 70 = 2*5*7, phi(70) = 24 = 8*3, so the odd kernel of phi(70) is a(70)=3. [corrected by _Bob Selcoe_, Aug 22 2017]
From _Bob Selcoe_, Aug 22 2017: (Start)
a(89) = 88/8 = 11.
For n = 8820, 8820 = 2^2*3^2*5*7^2; S = 3*5*7 = 105, n" = 3^2*5*7^2 = 2205. a(3)*a(5)*a(7) = 1*1*3 = 3; a(8820) = 3*2205/105 = 63.
(End)

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Cf. A000010, A000265, A227944, A329697, A336466, A336468, A336469, A339879, A339971, A339974.

a053575 = a000265 . a000010  -- Reinhard Zumkeller, Oct 09 2013

a:= n-> (t-> t/2^padic[ordp](t, 2))(numtheory[phi](n)):
seq(a(n), n=1..80);  # Alois P. Heinz, Apr 14 2020

Array[NestWhile[Ceiling[#/2] &, EulerPhi@ #, EvenQ] &, 94] (* Michael De Vlieger, Aug 22 2017 *) (* or *)
t=Array[EulerPhi,94]; t/2^IntegerExponent[t,2] (* Giovanni Resta, Aug 23 2017 *)

a(n)=n=eulerphi(n);n>>valuation(n,2) \\ Charles R Greathouse IV, Mar 05 2013

From Bob Selcoe, Aug 22 2017: (Start)
Let n" be the odd part of n, S be the odd squarefree kernel of n and p_i {i = 1..z} be all the prime factors of S. Then the sequence can be constructed by the following:
a(1) = 1;
a(n) = (n-1)" when n is prime; and
a(n) = Product_{i = 1..z} a(p_i)*n"/S when n is composite (see Examples).
(End)
From Antti Karttunen, Dec 27 2020: (Start)
a(n) = A336466(n) for squarefree n (see A005117).
A336466(a(n)) = A336468(n), A329697(a(n)) = A336469(n) = A329697(n) - A005087(n).
(End)

A049115 a(n) is the number of iterations of the Euler phi function needed to reach a power of 2, when starting from n.

Original entry on oeis.org

0, 0, 1, 0, 1, 1, 2, 0, 2, 1, 2, 1, 2, 2, 1, 0, 1, 2, 3, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 1, 2, 0, 2, 1, 2, 2, 3, 3, 2, 1, 2, 2, 3, 2, 2, 3, 4, 1, 3, 2, 1, 2, 3, 3, 2, 2, 3, 3, 4, 1, 2, 2, 3, 0, 2, 2, 3, 1, 3, 2, 3, 2, 3, 3, 2, 3, 2, 2, 3, 1, 4, 2, 3, 2, 1, 3, 3, 2, 3, 2, 3, 3, 2, 4, 3, 1, 2, 3, 2, 2, 3, 1, 2, 2, 2

Offset: 1

Labos Elemer

nonn

a(n) = A227944(n) if n is not a power of 2. - Eric M. Schmidt, Oct 13 2013

			If n is a power of 2, then a(n)=0 by definition. If n = 59049, then by iterating with phi, we get 59049 -> 39366 -> 13122 -> 4374 -> 1458 -> 486 -> 162 -> 54 -> 18 -> 6 -> 2 -> 1. It took ten steps to reach the first power of 2 (2 in this case), so a(59049) = 10.

T. D. Noe, Table of n, a(n) for n = 1..10000

Cf. A000010, A003434, A049113, A057716, A209229, A227944.

Cf. also A064097, A064415, A329697.

Table[If[IntegerQ@ Log2@ n, 0, -1 + Length@ NestWhileList[EulerPhi, n, ! IntegerQ@ Log2@ # &]], {n, 105}] (* Michael De Vlieger, Aug 01 2017 *)

A049115(n) = if(!bitand(n,n-1),0,1+A049115(eulerphi(n))); \\ Antti Karttunen, Aug 28 2021

The smallest x so that Nest[ EulerPhi, n, x ] = 2^w is just achieved.
From Antti Karttunen, Aug 28 2021: (Start)
If A209229(n) = 1, then a(n) = 0, otherwise a(n) = 1 + a(A000010(n)).
a(n) <= A003434(n) and a(n) <= A329697(n) for all n.
(End)

Definition corrected and simplified, example corrected by Antti Karttunen, Aug 28 2021

A256757 Number of iterations of A007733 required to reach 1.

Original entry on oeis.org

0, 1, 2, 1, 2, 2, 3, 1, 3, 2, 3, 2, 3, 3, 2, 1, 2, 3, 4, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 2, 3, 1, 3, 2, 3, 3, 4, 4, 3, 2, 3, 3, 4, 3, 3, 4, 5, 2, 4, 3, 2, 3, 4, 4, 3, 3, 4, 4, 5, 2, 3, 3, 3, 1, 3, 3, 4, 2, 4, 3, 4, 3, 4, 4, 3, 4, 3, 3, 4, 2, 5, 3, 4, 3, 2, 4, 4, 3, 4, 3, 3, 4, 3, 5, 4, 2, 3, 4, 3, 3

Offset: 1

Ivan Neretin, Apr 09 2015

In other words, the minimal height (not counting k) of the power tower 2^(2^(...^(2^k)...)) required to make it eventually constant modulo n (=A245970(n)) for sufficiently large k.

a(n) <= A227944(n) + 1. - Max Alekseyev, Oct 11 2016

Ivan Neretin, Table of n, a(n) for n = 1..10000

Cf. A007733, A256607 (second iteration), A256758 (positions of records), A003434, A227944 (similarly built upon the totient function).

a256757 n = fst $ until ((== 1) . snd)
            (\(i, x) -> (i + 1, fromIntegral $ a007733 x)) (0, n)
-- Reinhard Zumkeller, Apr 13 2015

A007733 = Function[n, MultiplicativeOrder[2, n/(2^IntegerExponent[n, 2])]];
a = Function[n, k = 0; m = n; While[m > 1, m = A007733[m]; k++]; k];
Table[a[n], {n, 100}] (* Ivan Neretin, Apr 13 2015 *)

a(n) = {if (n==1, return(0)); nb = 1; while((n = znorder(Mod(2, n/2^valuation(n, 2)))) != 1, nb++); nb;} \\ Michel Marcus, Apr 11 2015

For n>1, a(n) = a(A007733(n)) + 1.

A254411 Limit of f(f(f(...f(0)...))) modulo n as the number of iterations of f(x) = 2^x+1 grows.

Original entry on oeis.org

0, 1, 0, 1, 3, 3, 2, 1, 0, 3, 9, 9, 6, 9, 3, 1, 3, 9, 0, 13, 9, 9, 7, 9, 18, 19, 0, 9, 20, 3, 9, 1, 9, 3, 23, 9, 32, 19, 6, 33, 34, 9, 40, 9, 18, 7, 35, 33, 23, 43, 3, 45, 42, 27, 53, 9, 0, 49, 32, 33, 54, 9, 9, 1, 58, 9, 44, 37, 30, 23, 30, 9, 2, 69, 18, 57, 9, 45, 65, 33, 0, 75, 25, 9, 3, 83, 78, 9, 68, 63, 58, 53, 9, 35, 38, 33, 71, 23, 9, 93

Offset: 1

Max Alekseyev, Jan 30 2015

Also, limit of f(f(f(...f(m)...))) modulo n for any integer m >= 0.

Rémy Sigrist, Table of n, a(n) for n = 1..10000

Cf. A245970, A254410.

{ A254411(m) = my(g); if(m==1, return(0)); g=2^valuation(m,2); m\=g; lift( chinese(Mod(0,g),Mod(2,m)^A254411(eulerphi(m)) ) + 1) }

a(n) = limit of A254429(m) mod n as m grows.

a(n) = A254429(A227944(n)+k) mod n for any k>=1. In particular, a(n) = A254429(n) mod n.

A254410 Limit of f(f(f(...f(2)...))) modulo n as the number of iterations of f(x) = 2^x - 1 grows.

Original entry on oeis.org

0, 1, 1, 3, 2, 1, 1, 7, 1, 7, 6, 7, 10, 1, 7, 15, 8, 1, 1, 7, 1, 17, 17, 7, 2, 23, 1, 15, 26, 7, 3, 31, 28, 25, 22, 19, 34, 1, 10, 7, 4, 1, 1, 39, 37, 17, 35, 31, 1, 27, 25, 23, 32, 1, 17, 15, 1, 55, 36, 7, 5, 3, 1, 63, 62, 61, 43, 59, 40, 57, 49, 55, 1, 71, 52, 39, 50, 49, 75, 47, 1, 45, 66, 43, 42, 1, 55, 39, 63, 37, 36, 63, 34, 35, 77, 31, 65, 1, 28, 27

Offset: 1

Max Alekseyev, Jan 30 2015

Also, limit of f(f(f(...f(m)...))) modulo n for any integer m >= 2.

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

Cf. A245970, A254411.

Clear[a]; Unprotect[Power]; 0^0 = 1; a[1]=0; a[n_] := a[n] = Module[{g, m = n}, g = 2^IntegerExponent[m, 2]; m = Floor[m/g]; Mod[ ChineseRemainder[ {0, Mod[2, m]^a[EulerPhi[m]]}, {g, m}] - 1, n]]; Array[a, 100] (* Jean-François Alcover, Jan 01 2016, adapted from PARI *)

{ A254410(m) = my(g); if(m==1, return(0)); g=2^valuation(m,2); m\=g; lift( chinese(Mod(0,g),Mod(2,m)^A254410(eulerphi(m)) ) - 1) }

a(n) = limit of A007013(m) mod n as m grows.

a(n) = A007013(A227944(n) + k) mod n for any k >= 1. In particular, a(n) = A007013(n) mod n.

A347386 Number of iterations of A347385 (Dedekind psi function applied to the odd part of n) needed to reach a power of 2.

Original entry on oeis.org

0, 0, 1, 0, 2, 1, 1, 0, 2, 2, 2, 1, 2, 1, 2, 0, 3, 2, 3, 2, 1, 2, 2, 1, 3, 2, 3, 1, 3, 2, 1, 0, 2, 3, 2, 2, 4, 3, 2, 2, 2, 1, 3, 2, 3, 2, 2, 1, 2, 3, 3, 2, 4, 3, 3, 1, 3, 3, 3, 2, 2, 1, 2, 0, 2, 2, 4, 3, 2, 2, 3, 2, 5, 4, 3, 3, 2, 2, 3, 2, 4, 2, 2, 1, 4, 3, 3, 2, 4, 3, 2, 2, 1, 2, 3, 1, 3, 2, 3, 3, 4, 3, 3, 2, 2

Offset: 1

Antti Karttunen, Aug 31 2021

nonn

Also, for n > 1, one less than the number of iterations of A347385 to reach 1.

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

Cf. A000265, A001615, A209229, A347385, A347387 (the exponent of the eventual power of 2 reached).

Cf. also A003434, A019269, A227944, A256757, A331410, A336361 for similar sequences.

f[p_, e_] := If[p == 2, 1, (p + 1)*p^(e - 1)]; psiOdd[1] = 1; psiOdd[n_] := Times @@ f @@@ FactorInteger[n]; a[n_] := -1 + Length @ NestWhileList[psiOdd, n, # != 2^IntegerExponent[#, 2] &]; Array[a, 100] (* Amiram Eldar, Aug 31 2021 *)

A347385(n) = if(1==n,n, my(f=factor(n>>valuation(n, 2))); prod(i=1, #f~, f[i, 1]^f[i, 2] + f[i, 1]^(f[i, 2]-1)));
A347386(n) = if(!bitand(n, n-1), 0, 1+A347386(A347385(n)));

If A209229(n) = 1, then a(n) = 0, otherwise a(n) = 1 + a(A001615(A000265(n))).

For all n >= 1, a(n) <= A331410(n).

A318970 a(1) = 3; for n > 1, a(n) = 2^(a(n-1) - 1) + 5.

Original entry on oeis.org

3, 9, 261, 1852673427797059126777135760139006525652319754650249024631321344126610074238981

Offset: 1

Max Alekseyev, Sep 06 2018

nonn

a(n) divides a(n+1) for n <= 4, but it is unknown if this divisibility holds for larger n. In other words, it is unknown if this sequence is a subsequence of A245594.
Modulo any m > 1, the sequence stabilizes within the first A227944(m) <= log_2(m) terms. That is, for any n >= A227944(m), we have a(n) == a(A227944(m)) == A318989(m) (mod m).
It follows that the prime divisors of the terms (cf. A318971) are very sparse: if prime p does not divide any of the first log_2(p) terms, then p does not divide any term.

Max Alekseyev, Iterations of 2^(n-1)+5: the strong law of small numbers, or something bigger?, MathOverflow, 2016.

Cf. A245594, A318971, A318989.

[n le 1 select 3 else 2^(Self(n-1)-1)+5: n in [1..4]]; // Vincenzo Librandi, Sep 07 2018

RecurrenceTable[{a[1]==3, a[n]==2^(a[n-1] - 1) + 5}, a, {n, 4}] (* Vincenzo Librandi, Sep 07 2018 *)

A318971 Primes that divide at least one term of A318970.

Original entry on oeis.org

3, 29, 31821709567, 28480625878963

Offset: 1

Max Alekseyev, Sep 06 2018

No other terms below 10^14.
If prime p does not divide any of the first A227944(p) <= log_2(p) terms of A318970, then p does not divide any term of A318970, i.e., p does not belong to this sequence.
(2^260+5)/261 is a term (76-digit prime). Hence, a(5) <= (2^260+5)/261.
Any prime p with A318989(p)=0 belongs to this sequence. However, it is unknown if there is a term p with nonzero A318989(p).

			a(1)=3 divides A318970(k) for all k >= 1.
a(2)=29 divides A318970(k) for all k >= 3.
a(3)=31821709567 divides A318970(k) for all k >= 8.
a(4)=28480625878963 divides A318970(k) for all k >= 11.

Max Alekseyev, Iterations of 2^(n-1)+5: the strong law of small numbers, or something bigger?, MathOverflow, 2016.

Cf. A227944, A245594, A318970, A318989.

A318989 Limiting value of A318970(k) mod n as k grows.

Original entry on oeis.org

0, 1, 0, 1, 1, 3, 2, 5, 0, 1, 6, 9, 1, 9, 6, 5, 4, 9, 14, 1, 9, 17, 14, 21, 6, 1, 18, 9, 0, 21, 6, 5, 6, 21, 16, 9, 2, 33, 27, 21, 6, 9, 3, 17, 36, 37, 19, 21, 16, 31, 21, 1, 6, 45, 6, 37, 33, 29, 34, 21, 52, 37, 9, 5, 1, 39, 40, 21, 60, 51, 42, 45, 42, 39, 6, 33, 72, 27, 28, 21, 72, 47, 56, 9, 21, 3, 0, 61, 37, 81, 79, 37, 6, 19, 71, 69, 11, 65, 72, 81

Offset: 1

Max Alekseyev, Sep 06 2018

nonn

Is there a prime p in A318971 such that a(p) is nonzero?

Cf. A245970, A254410, A254411, A318970, A318971.

a(n) = A318970(k) mod n holds for any k >= A227944(n). In particular, a(n) = A318970(A227944(n)) mod n.

cp's OEIS Frontend

A227946 Smallest m such that the number of iterations of "take odd part of phi" to reach 1 from m (A227944) is n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Haskell

Formula

Extensions

A053575 Odd part of phi(n): a(n) = A000265(A000010(n)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

A049115 a(n) is the number of iterations of the Euler phi function needed to reach a power of 2, when starting from n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A256757 Number of iterations of A007733 required to reach 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

A254411 Limit of f(f(f(...f(0)...))) modulo n as the number of iterations of f(x) = 2^x+1 grows.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A254410 Limit of f(f(f(...f(2)...))) modulo n as the number of iterations of f(x) = 2^x - 1 grows.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A347386 Number of iterations of A347385 (Dedekind psi function applied to the odd part of n) needed to reach a power of 2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs