A203966 -id:A203966 - cp's OEIS frontend

A050474 Solutions to 2*phi(x) = x+1.

1, 3, 15, 255, 65535, 83623935, 4294967295, 6992962672132095

Offset: 1

Jud McCranie, Dec 24 1999

If n is in the sequence and n+2 is prime then m=n*(n+2) is in the sequence because 2*phi(m) = 2*phi(n*(n+2)) = 2*phi(n)*(n+1) = (n+1)^2 = m+1. We can obtain the terms 3, 15, 255, 65535 & 4294967295 from 1 (the first term) in this way. Also since 83623935 is a term and 83623935+2 is prime 83623935*(83623935+2)=6992962672132095 is in the sequence. So 1 and 83623935 are the only known independent terms and next term of this sequence if it exists is the third such term. - Farideh Firoozbakht, May 01 2007
The next term, if it exists, has at least 7 distinct prime factors (see Beiler, p. 92). - Jud McCranie, Dec 13 2012
From Chris Boyd, Mar 22 2015: (Start)
Solutions to k*phi(x) = x + 1, including a(1) - a(8), were published in 1932 by D. H. Lehmer. In the paper's summing up, "3*5*353*929" (= 4919055) was printed in error; it should have read "3*5*17*353*929" (= 83623935), i.e., a(6). This error has been propagated in several subsequent texts, including Wong's thesis.
Lehmer identified solutions where x has fewer than 7 distinct prime factors. Wong showed that no additional solutions exist unless x has at least 8 distinct prime factors. It appears not to be excluded by either author that an unidentified solution < a(8) with 8 or more distinct prime factors may exist. (End)
There are no other terms below 10^25. - Max Alekseyev, May 04 2024

			2*phi(15) = 2*8 = 15 + 1, so 15 is a member of the sequence.

A. H. Beiler, Recreations in the Theory of Numbers, page 92.

D. H. Lehmer, On Euler's totient function, Bulletin of the American Mathematical Society, 38 (1932), 745-751.
E. Wong, Computations on normal families of primes, Simon Fraser University, 1997, MSc thesis.

Subsequence of A203966.

Cf. A000010, A129613, A129614, A129615, A202855.

[n: n in [1..2*10^6] | 2*EulerPhi(n) eq (n+1)]; // Vincenzo Librandi, Mar 22 2015

Select[Range[700000], (# + 1)== 2 EulerPhi[#] &] (* Vincenzo Librandi, Mar 22 2015 *)

is_A050474(n)=if(2*eulerphi(n)==n+1,1,0) \\ Chris Boyd, Mar 22 2015

A number n is in the sequence iff phi(n^2)=1+2+3+...+n because n is in the sequence <=> 2*phi(n)=n+1 <=> n*phi(n)=n*(n+1)/2 <=> phi(n^2)=1+2+3++...+n. For n=1,2,...,5, a(n)=2^2^(n-1)-1. - Farideh Firoozbakht, Jan 26 2006

A202855 Numbers n such that phi(n) - 1 divides n, where phi is Euler's totient function.

Original entry on oeis.org

3, 4, 6, 12, 60, 1020, 262140, 334495740, 17179869180, 27971850688528380

Offset: 1

José María Grau Ribas, Dec 25 2011

The sequence b(n) = 4*A050474(n) is a subsequence of this sequence, and comprises solutions of n/(phi(n) - 1) = 4, accounting for all terms up to a(9) except a(1) and a(3). Proof: suppose n/(phi(n) - 1) = 4. With n = 4*x, x/(phi(4*x) - 1) = 1, or phi(4*x) = x + 1. Since phi(k) is even for k > 2, x is odd, and phi(4*x) = 2*phi(x) = x + 1, the definition of A050474. It follows that 4*A050474(8) = 27971850688528380 is a term of this sequence. - Chris Boyd, Mar 22 2015

Similarly, the terms with n/(phi(n) - 1) = 3 are given by 3 * terms of A050474 coprime to 3; n/(phi(n) - 1) = 6 are given by 6 * terms of A050474 coprime to 6. Also, the terms of n/(phi(n) - 1) = 5 are given by 5 * terms t of A203966 coprime to 5 and having (t+1)/phi(t) = 4. Note that n/(phi(n) - 1) = 2 is impossible. - Max Alekseyev, Oct 26 2023

Cf. A000010, A050474, A203966.

Select[1 + Range[1000000], Divisible[#, EulerPhi[#] - 1] &]

for(n=3,1e7,if(n%(eulerphi(n)-1)==0,print1(n", "))) \\ Charles R Greathouse IV, Dec 26 2011

a(8) from Charles R Greathouse IV, Dec 27 2011
a(9) from Donovan Johnson, Dec 29 2011
a(10) from Chris Boyd confirmed by Max Alekseyev, Oct 26 2023

A097029 Fixed points when the function f(x) = phi(x) + floor(x/2) is iterated, i.e., solutions to f(x) = x.

Original entry on oeis.org

1, 2, 3, 4, 8, 15, 16, 32, 64, 128, 255, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65535, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 83623935, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967295

Offset: 1

Labos Elemer, Aug 27 2004

nonn

Trivial fixed points are the powers of 2. How many nontrivial cases exist like 3, 15, 255, 65535: the first 5 terms of A051179. More?

83623935 is the next such term (see also A050474 and A203966). - Michel Marcus, Nov 13 2015

			For fixed points the cycle lengths are A097026(n=fix)=1, but the reverse is not true because long transients may also lead to 1-cycles.
So, e.g., 1910 is not here because its terminal 1-cycle is prefixed by a long transient: {1910, 1715, 2033, 2924, 2806, 2723, 3689, 4724, 4722, 3933, 4342, 4163, 6041, 8192, 8192}.

Max Alekseyev, Table of n, a(n) for n = 1..91

Union of A000079 and A050474.

Cf. A000010, A051179, A097026, A097027, A097028.

isok(n) = eulerphi(n) + n\2 == n; \\ Michel Marcus, Nov 13 2015

a(30)-a(35) from Michel Marcus, Nov 13 2015

a(36)-a(38) from Jinyuan Wang, Jul 22 2021

A207574 Numbers k such that phi(k)+2 divides k+2.

Original entry on oeis.org

1, 6, 10, 14, 22, 26, 34, 38, 46, 58, 62, 74, 82, 86, 94, 106, 118, 122, 134, 142, 146, 158, 166, 178, 194, 202, 206, 214, 218, 226, 254, 262, 274, 278, 298, 302, 314, 326, 334, 346, 358, 362, 382, 386, 390, 394, 398, 422, 446, 454, 458, 466, 478

Offset: 1

José María Grau Ribas, Feb 19 2012

Consists of the even semiprimes (other than 4) together with A207575. - Charles R Greathouse IV, Jul 15 2013

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A000010, A207575, A202855, A203966.

Select[Range[1000],Divisible[#+2,EulerPhi[#]+2]&]

isA207574(n)={
        if( (n+2) % (eulerphi(n)+2) ==0,1,0) ;
}
{
for(n=1,200,
        if (isA207574(n) , print(n)) ;
) ;
} /* R. J. Mathar, Feb 23 2012 */

A060473 a(n) = numerator of phi(n)/(n+1), where phi(n) is Euler's phi, A000010.

Original entry on oeis.org

1, 1, 1, 2, 2, 2, 3, 4, 3, 4, 5, 4, 6, 2, 1, 8, 8, 6, 9, 8, 6, 10, 11, 8, 10, 4, 9, 12, 14, 8, 15, 16, 10, 16, 2, 12, 18, 6, 3, 16, 20, 12, 21, 4, 12, 22, 23, 16, 21, 20, 8, 24, 26, 18, 5, 8, 18, 28, 29, 16, 30, 10, 9, 32, 8, 20, 33, 32, 22, 24, 35, 24, 36, 12, 10, 36, 10, 24, 39, 32, 27, 40, 41

Offset: 1

Fabian Rothelius, Mar 16 2001

a(A203966(n)) = 1. - Robert G. Wilson v, Jul 05 2014

			a(7) = 3 because phi(7)/(7+1) = 6/8 = 3/4.

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

Cf. A000010, A060474.

with(numtheory,phi): seq(numer(phi(n)/(n+1)), n=1..50);

Numerator/@Table[EulerPhi[n]/(n+1),{n,90}] (* Harvey P. Dale, May 11 2011 *)

{ for (n=1, 1000, write("b060473.txt", n, " ", numerator(eulerphi(n)/(n + 1))); ) } \\ Harry J. Smith, Jul 05 2009

More terms from Asher Auel, Mar 16 2001

A238232 Composite numbers n such that the sum of numbers x<=n not coprime to n divides the sum of numbers y<=n coprime to n.

Original entry on oeis.org

15, 35, 95, 119, 143, 209, 255, 287, 319, 323, 377, 527, 559, 779, 899, 923, 989, 1007, 1189, 1199, 1295, 1343, 1349, 1763, 1919, 2159, 2507, 2759, 2911, 3239, 3599, 3827, 4031, 4607, 5183, 5207, 5249, 5459, 5543, 6439, 6479, 6887, 7067, 7279, 7739, 8159, 8639

Offset: 1

Paolo P. Lava, Feb 21 2014

nonn

Also numbers n such that n+1-phi(n) | phi(n).

A203966 lists the numbers n such that the sum of numbers x<=n coprime to n divides the sum of numbers y<=n not coprime to n. This is equivalent to numbers n such that phi(n) | n+1. [suggested by Giovanni Resta]

			The numbers coprime to 15 are 1, 2, 4, 7, 8, 11, 13, 14 and their sum is 60. In fact 15*phi(15)/2 = 60.
The sum of the numbers from 1 to 15 is 15*(15+1)/2 = 120 and therefore the sum of the numbers not coprime to 15 is 120 - 60 = 60. At the end we have that 60/60 = 1.

Paolo P. Lava, Table of n, a(n) for n = 1..1000

Cf. A061367, A050474, A070161, A142591, A203966.

with(numtheory);P:=proc(q) local i,n;
for n from 2 to q do if not isprime(n) then
if type(phi(n)/(n+1-phi(n)),integer) then print(n);
fi; fi; od; end: P(10^6);

A207575 Numbers k such that phi(k) + 2 divides k + 2 and k is not twice a prime.

Original entry on oeis.org

1, 390, 10374, 2283934267736070, 7316037865689066623729670

Offset: 1

José María Grau Ribas, Feb 19 2012

Contains 2 * terms t of A350777 such that (t-3)/phi(t) = 2. - Max Alekseyev, Oct 26 2023

Cf. A000010, A207574, A202855, A203966, A350777.

Select[Range[20000000], !PrimeQ[#/2] && Divisible[#+2, EulerPhi[#]+2]&]

for(n=1,1e5,if((n+2)%(eulerphi(n)+2)==0&&(n%2||!isprime(n/2)), print1(n", "))) \\ Charles R Greathouse IV, Mar 02 2012

a(4)-a(5) from Max Alekseyev, Nov 06 2023

A226104 Numbers n such that phi(n)+3 divides n+3.

Original entry on oeis.org

1, 30, 42, 66, 78, 102, 114, 138, 174, 186, 195, 222, 246, 258, 282, 318, 354, 366, 402, 426, 438, 474, 498, 534, 582, 606, 618, 642, 654, 678, 762, 786, 822, 834, 894, 906, 942, 978, 1002, 1038, 1074, 1086, 1146, 1158, 1182, 1194, 1266, 1338, 1362, 1374, 1398

Offset: 1

José María Grau Ribas, May 26 2013

nonn

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Cf. A000010 (Euler's totient function).
Cf. A207574 (numbers n such that phi(n)+2 divides n+2).
Cf. A202855 (numbers n such that phi(n)-1 divides n).
Cf. A203966 (numbers n such that phi(n) divides n+1).

Select[Range[2000], IntegerQ[(# + 3)/(EulerPhi[#] + 3)] &]

is(n)=(n+3)%(eulerphi(n)+3)==0 \\ Charles R Greathouse IV, Nov 13 2013

from sympy import totient as phi
def ok(n): return (n+3) % (phi(n)+3) == 0
print([m for m in range(1, 1400) if ok(m)]) # Michael S. Branicky, Jan 30 2021

A249541 Numbers m such that phi(m-2) divides m-1 where phi is Euler's totient function (A000010).

Original entry on oeis.org

3, 4, 5, 17, 257, 65537, 83623937, 4294967297, 6992962672132097

Offset: 1

Jaroslav Krizek, Feb 25 2015

The first 5 known Fermat primes from A019434 are in this sequence.
Corresponding values of numbers k(m) = (m-1) / phi(m-2): 2, 3, 2, 2, 2, 2, 2, 2, ...
Conjecture: 4 is the only number m such that 3*phi(m-2) = m-1. (See comment in A203966.)

			4 is in the sequence because phi(4-2) = 1 divides 4-1 = 3.

Supersequence of A232720 and A254576.

Cf. A000010, A019434, A203966, A232720, A254576.

[n: n in [3..10000000] | (n-1) mod EulerPhi(n-2) eq 0];

a(n) = A203966(n+1) + 2. - Max Alekseyev, Feb 01 2024

a(9) confirmed by Max Alekseyev, Feb 01 2024

A250405 Numbers k such that all values of Euler phi (A000010) of all divisors of k are pairwise distinct and represent all proper divisors of k+1.

Original entry on oeis.org

1, 3, 15, 255, 65535, 4294967295

Offset: 1

Jaroslav Krizek, Nov 22 2014

Numbers k such that {phi(d) : d|k} = {d : d|(k+1), d<(k+1)} as multisets.
Conjecture: last term is 4294967295.
First six terms coincide with A051179. - Omar E. Pol, Apr 12 2025

			15 is in the sequence because {phi(d) : d|15} = {1, 2, 4, 8} = {d : d|16, d<16}.
2 is not in the sequence because {phi(d) : d|2} = {1, 1}, but {d : d|2, d<2} = {1}.

Subsequence of A250404 and A203966.
Sequence differs from A051179, A050474 and A116518.
Cf. A000010.

[n: n in [1..100000] | ([EulerPhi(d): d in Divisors(n)]) eq ([d: d in Divisors(n+1) | d lt n+1 ])];

Edited and a(6) added by Max Alekseyev, May 04 2024

cp's OEIS Frontend

A050474 Solutions to 2*phi(x) = x+1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A202855 Numbers n such that phi(n) - 1 divides n, where phi is Euler's totient function.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

Extensions

A097029 Fixed points when the function f(x) = phi(x) + floor(x/2) is iterated, i.e., solutions to f(x) = x.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions

A207574 Numbers k such that phi(k)+2 divides k+2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A060473 a(n) = numerator of phi(n)/(n+1), where phi(n) is Euler's phi, A000010.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A238232 Composite numbers n such that the sum of numbers x<=n not coprime to n divides the sum of numbers y<=n coprime to n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

A207575 Numbers k such that phi(k) + 2 divides k + 2 and k is not twice a prime.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

Extensions

A226104 Numbers n such that phi(n)+3 divides n+3.