A007755 -id:A007755 - cp's OEIS frontend

A060611 Smallest prime p such that n = A049108(p) = length of chain of iterates of Euler Phi starting with p.

2, 3, 5, 11, 17, 41, 83, 137, 257, 641, 1097, 2657, 5441, 10883, 17477, 40961, 65537, 140417, 295937, 557057, 1193537, 2384897, 4227137, 9548417, 17966357, 35946497, 71304257, 162174977, 305268737, 541073537, 1212153857, 2281701377

Offset: 2

Labos Elemer, Apr 13 2001

nonn

From 2nd to 12th term A007755 is the same as this sequence

			n=13: a(13)=2657 is the smallest prime which gives a chain of length 13, 2657 -> 2656 -> 1312 -> 640 -> 256 -> 128 -> 64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1, while the smallest number having this property is A007755(13) = 2329 -> 2176 -> 1024 -> 512 -> 256 -> 128 -> 64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1.

T. D. Noe, Table of n, a(n) for n=2..1002
Project Euler, Problem 214: Totient chains.
T. D. Noe, Computing Numbers in Section I of the Totient Iteration

Cf. A000010, A049108 = A003434 + 1, A007755, A049117.

A007755 has the same initial terms but is a different sequence.

More terms from Jud McCranie, Apr 22 2001

Removed duplicate cross references, added link, reformulated example. - M. F. Hasler, Oct 25 2008

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

Original entry on oeis.org

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

A136040 Classes of the phi iteration for which the smallest number is prime.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 14, 16, 17, 19, 21, 22, 25, 26, 29, 31, 41, 49, 51, 52, 55, 58, 59, 60, 63, 65, 66, 67, 69, 71, 74, 77, 79, 81, 82, 87, 89, 108, 109, 113, 114, 116, 119, 122, 124, 127, 129, 130, 136, 137, 142, 143, 145, 147, 148, 151, 154, 158, 159, 161, 162, 163

Offset: 1

T. D. Noe, Dec 12 2007

nonn

Rows of A058812 which begin with a prime. The actual primes are in A092873, which is A007755(n+2) for the n in this sequence.

T. D. Noe, Table of n, a(n) for n=1..288
T. D. Noe, Primes in classes of the iterated totient function, JIS 11 (2008) 08.1.2
Harold Shapiro, An arithmetic function arising from the phi function, Amer. Math. Monthly, Vol. 50, No. 1 (1943), 18-30.

Added 63 and 159. - T. D. Noe, Nov 18 2008

A334099 The least k for which A329697(k) = n; Position of first occurrence of n (and also records) in A329697.

Original entry on oeis.org

1, 3, 7, 19, 43, 127, 283, 659, 1319, 3957, 9227, 21599, 50123, 129263, 258527, 775581, 1551163, 4340087, 9750239, 27353747, 65148847, 156067127, 340997113, 955523423

Offset: 0

Antti Karttunen, Apr 14 2020

Note that although most of the terms after 1 are primes, we also have a few composites: a(9) = a(1)*a(8) = 3*1319 = 3957, a(15) = a(1)*a(14) = 3*258527 = 775581, a(22) = a(8)*a(14) = 340997113.
a(n) <= 3^n and in particular, a(n+1) <= 3*a(n), n > 0 and more generally a(n + m) <= a(n) * a(m) where m, n >= 0. - David A. Corneth, Apr 15 2020
The above follows because A329697 is totally additive.

The leftmost column of A334100.
Cf. A329697 (a left inverse).
Cf. A067513.
Cf. A007755, A105017, and also A329662 (analogous sequence when using the map k -> k + k/p).

With[{s = Array[Length@ NestWhileList[# - #/FactorInteger[#][[-1, 1]] &, #, # != 2^IntegerExponent[#, 2] &] - 1 &, 10^6]}, {1}~Join~Array[FirstPosition[s, #][[1]] &, Max@ s]] (* Michael De Vlieger, Apr 30 2020 *)

A329697(n) = if(!bitand(n,n-1),0,1+A329697(n-(n/vecmax(factor(n)[, 1]))));
m=-1; k=0; for(n=1,2^32, t=A329697(n); if(t>m, m=t; write("b334099.txt", k, " ", n); k++));

For all n >= 0, A329697(a(n)) = n.

A348214 a(n) is the least number k such that A348213(k) = n, or -1 if no such number exists.

Original entry on oeis.org

1, 2, 64, 50624, 235053, 15800785, 36903321, 4038974856

Offset: 0

Amiram Eldar, Oct 07 2021

			n The n iterations of a(n) under the map x -> A348158(x)
- --------------------------------------------------------------------------------
0 1
1 2 -> 1
2 64 -> 63 -> 57
3 50624 -> 49833 -> 49155 -> 48819
4 235053 -> 231363 -> 223245 -> 222885 -> 210693
5 15800785 -> 15775305 -> 15763125 -> 15761925 -> 15208875 -> 14889335
6 36903321 -> 36323991 -> 35049465 -> 34992945 -> 33078801 -> 32940117 -> 29802963
7 4038974856 -> 2855346375 -> 2854284615 -> 2556863361 -> 2549117805 -> 2536180173 -> 2447191395 -> 2445883515

Cf. A007755, A348158, A348213.

f[n_] := Plus @@ DeleteDuplicates @ Map[EulerPhi, Divisors[n]]; s[n_] := -2 + Length @ FixedPointList[f, n]; seq[m_, lim_] := Module[{t = Table[0, {m}], c = 0, n = 1}, While[c < m && n < lim, i = s[n] + 1; If[i <= m && t[[i]] == 0, c++; t[[i]] = n]; n++]; TakeWhile[t, # > 0 &]]; seq[5, 10^6]

A385747 Least number that reaches 1 after exactly n iterations of the infinitary analog of the totient function A384247.

Original entry on oeis.org

1, 2, 3, 4, 5, 9, 16, 17, 41, 73, 101, 197, 467, 829, 1109, 2761, 4849, 7831, 12401, 26189, 52379, 85853, 139589, 237007, 395533, 947043, 1967027, 3446033, 5396427, 9510437, 17502533, 35005067, 71202449, 90187609, 164664701, 395199461, 705113873, 1265735729, 1803553457

Offset: 0

Amiram Eldar, Jul 08 2025

nonn

a(n) is the least number k such that A385744(k) = n.

Also, indices of records of A385744.

			  n | a(n) | iterations
  --+------+---------------------------
  1 |    2 | 2 -> 1
  2 |    3 | 3 -> 2 -> 1
  3 |    4 | 4 -> 3 -> 2 -> 1
  4 |    5 | 5 -> 4 -> 3 -> 2 -> 1
  5 |    9 | 9 -> 8 -> 4 -> 3 -> 2 -> 1

Cf. A384247, A385744, A385745, A385746.

Similar sequences: A003271, A005424, A007755, A333610.

f[p_, e_] := p^e*(1 - 1/p^(2^(IntegerExponent[e, 2]))); iphi[1] = 1; iphi[n_] := iphi[n] = Times @@ f @@@ FactorInteger[n];
numiter[n_] := Length @ NestWhileList[iphi, n, # != 1 &] - 1;
seq[len_] := Module[{s = {}, k = 0, i = 0}, While[Length[s] < len, k++; If[numiter[k] == i, AppendTo[s, k]; i++]]; s]; seq[25]

iphi(n) = {my(f = factor(n)); n * prod(i = 1, #f~, (1 - 1/f[i, 1]^(1 << valuation(f[i, 2], 2))));}
numiter(n) = if(n ==  1, 0, 1 + numiter(iphi(n)));
list(len) = {my(k = 0, i = 0, c = 0); while(c < len, k++; if(numiter(k) == i, c++; print1(k, ", "); i++));}

A225563 Numbers whose totient-trajectory can be partitioned into two sets with the same sum.

Original entry on oeis.org

3, 5, 7, 9, 11, 13, 15, 17, 25, 27, 31, 33, 35, 39, 41, 49, 51, 55, 61, 65, 69, 77, 81, 85, 87, 91, 95, 97, 103, 111, 115, 119, 121, 123, 125, 133, 137, 141, 143, 145, 153, 155, 159, 161, 175, 183, 185, 187, 193, 201, 203, 205, 209, 213, 215, 217, 219, 221

Offset: 1

Kevin L. Schwartz and Christian N. K. Anderson, May 10 2013

nonn

The "totient-trajectory" of a number m is the sequence obtained by starting with m and repeatedly applying the map x -> phi(x) (cf. A000010) until reaching 1.
Because all totient-trajectories contain only even numbers apart from the final 1 and (perhaps) the initial term ending in 1, only odd numbers will be in the sequence.
Conjecture: No totient-trajectory can be partitioned into an odd number of sets with the same sum.
Observation: for the first 1000 terms, numbers ending in 5 are more than twice as frequent as those ending in any other number.

			17 is in the sequence because its totient-trajectory is {17,16,8,4,2,1}, which can be partitioned into 17+4+2+1 = 16+8.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from Christian N. K. Anderson)
Christian N. K. Anderson, Decomposition of the first 1000 terms.

Cf. A008683, A003434, A007755, A049108, A002202, A000010, A083207.

totQ[n_] := Module[{it = Most@FixedPointList[EulerPhi, n], sum, x}, sum = Plus @@ it; If[OddQ[sum], False, CoefficientList[Product[1 + x^i, {i, it}], x][[1 +sum/2]] > 0]]; Select[Range[221], totQ] (* Amiram Eldar, May 24 2020 *)

library(numbers); totseq<-function(x) { while(x[length(x)]>1) x[length(x)+1]=eulersPhi(x[length(x)]); x };
eqsum<-function(xvec) {
mkgrp<-function(grp) {
    if(length(grp)==length(xvec)) {
        tapply(xvec,grp,sum)->tot;
        if(length(tot)==2) if(tot[1]==tot[2]) {faxp<<-grp; return(T)}; return(F);
    }
    ifelse(mkgrp(c(grp,1)),T,mkgrp(c(grp,2)));
}
ifelse(length(xvec)<2,F,mkgrp(c()));
}
which(sapply(2*(1:100)-1,function(x) eqsum(totseq(x))))*2-1

Edited by N. J. A. Sloane, May 17 2013

A256758 Position of first appearance of n in A256757.

Original entry on oeis.org

1, 2, 3, 7, 19, 47, 163, 487, 1307, 2879, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 86093443, 344373773, 688747547, 3486784401

Offset: 0

Ivan Neretin, Apr 09 2015

Smallest number m such that the trajectory of m under iteration of A007733 takes n steps to reach the fixed point.

The terms a(1)..a(9) are primes. The next eight terms are powers of 3, so that for n=10..17, a(n)=3^(n-1), but this apparently established pattern breaks at a(18), which is again a prime.

Cf. A007733, A007755 (similarly built upon the totient function), A173927 (similarly built upon the Carmichael lambda function), A256757.

import Data.List (elemIndex); import Data.Maybe (fromJust)
a256758 = (+ 1) . fromJust . (`elemIndex`  a256757_list)
-- Reinhard Zumkeller, Apr 13 2015

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

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

a(15)-a(18) from Michel Marcus, Apr 11 2015

a(19)-a(21) from Amiram Eldar, Mar 04 2023

A333610 Least number that reaches 1 after n iterations of the infinitary totient function A091732.

Original entry on oeis.org

1, 2, 3, 4, 5, 11, 17, 47, 85, 227, 257, 919, 1229, 2459, 4369, 9839, 30865, 101503, 148157, 438499, 828297, 2201671, 3316617, 11055391, 35354993, 140810491, 188991053, 377982107, 848170377, 1704741139, 6933926513

Offset: 0

Amiram Eldar, Mar 28 2020

Cf. A003271, A007755, A091732, A333609.

f[p_, e_] := p^(2^(-1 + Position[Reverse @ IntegerDigits[e, 2], 1])); iphi[1] = 1; iphi[n_] := Times @@ (Flatten@(f @@@ FactorInteger[n]) - 1); numiter[n_] := Length @ NestWhileList[iphi, n, # != 1 &] - 1; n = 0; seq = {}; Do[If[numiter[k] == n, AppendTo[seq, k]; n++], {k, 1, 1000}]; seq

A333609(a(n)) = n.

A112245 Numbers k such that 65537*2^k+1 is prime.

Original entry on oeis.org

287, 1695, 81359, 512895

Offset: 1

T. D. Noe, Aug 30 2005, Aug 26 2007

Note that 65537=2^16+1 is the largest known Fermat prime. These n yield provable primes. The primes are the smallest numbers in classes 303, 1711 and 81375 of the phi iteration (see A007755).

Jacques Molne found 512895. The corresponding provable prime is the smallest number in class 512911 of the Phi iteration.

Cf. A002253, A002254, A002259, A053345 (F*2^n+1 is prime, where F is a Fermat prime).

is(n)=ispseudoprime(65537*2^n+1) \\ Charles R Greathouse IV, Jun 13 2017

cp's OEIS Frontend

A060611 Smallest prime p such that n = A049108(p) = length of chain of iterates of Euler Phi starting with p.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

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

A136040 Classes of the phi iteration for which the smallest number is prime.

Views

Author

Keywords

Comments

Links

Extensions

A334099 The least k for which A329697(k) = n; Position of first occurrence of n (and also records) in A329697.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

Formula

A348214 a(n) is the least number k such that A348213(k) = n, or -1 if no such number exists.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A385747 Least number that reaches 1 after exactly n iterations of the infinitary analog of the totient function A384247.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

A225563 Numbers whose totient-trajectory can be partitioned into two sets with the same sum.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

R

Extensions

A256758 Position of first appearance of n in A256757.

Views

Author

Keywords

Comments

Crossrefs

Programs

Haskell

Mathematica

PARI

Extensions

A333610 Least number that reaches 1 after n iterations of the infinitary totient function A091732.