A000010 -id:A000010 - cp's OEIS frontend

A203966 Numbers n such that phi(n) divides n+1, where phi is Euler's totient function (A000010).

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

Offset: 1

José María Grau Ribas, Jan 08 2012

Numbers k such that A060473(k) = 1. - Robert G. Wilson v, Jul 06 2014
Except for a(2), all terms are odd. - Chai Wah Wu, Jun 06 2017
Since gcd(phi(n),n) = 1, all terms are squarefree. Then, for n = p1 * ... * pk with primes p1 < ... < pk, (n+1)/phi(n) is very close to p1/(p1-1)*...*pk/(p1-1). Since p/(p-1) is decreasing as p grows, having (n+1)/phi(n) = 3 implies that p1 >= 5 and further that n >= 2.4*10^56 is a product of at least 33 primes. Similarly, having (n+1)/phi(n) >= 4 implies that n >= 1.6*10^30 is a product of at least 21 primes. Hence, the terms of this sequence below 1.6*10^30 have (n+1)/phi(n) = 2 and thus coincide with A050474. - Max Alekseyev, Jan 30 2022

			15 is in the sequence because phi(15) = 8, and 8 divides 16 = 15 + 1 evenly.

D. H. Lehmer, On Euler's totient function, Bulletin of the American Mathematical Society, 38 (1932), 745-751.

Cf. A060473, A000010, A202855.

Superset of A050474.

Select[Range[100000], Divisible[#+1, EulerPhi[#]]&]

a(8) from Donovan Johnson, Jan 13 2012

a(9) confirmed by Max Alekseyev, Jan 30 2022

A286160 Compound filter: a(n) = T(A000010(n), A046523(n)), where T(n,k) is sequence A000027 used as a pairing function.

Original entry on oeis.org

1, 2, 5, 12, 14, 23, 27, 59, 42, 40, 65, 109, 90, 61, 86, 261, 152, 142, 189, 179, 148, 115, 275, 473, 273, 148, 318, 265, 434, 674, 495, 1097, 320, 226, 430, 1093, 702, 271, 430, 757, 860, 832, 945, 485, 619, 373, 1127, 1969, 1032, 485, 698, 619, 1430, 838, 1030, 1105, 856, 556, 1769, 2791, 1890, 625, 1117, 4497, 1426, 1196, 2277, 935, 1220

Offset: 1

Antti Karttunen, May 04 2017

nonn

Antti Karttunen, Table of n, a(n) for n = 1..10000
MathWorld, Pairing Function

Cf. A000010, A000027, A046523, A286161, A286162, A286163, A286164.

Cf. for example A061468 (one of the sequences this matches with).

A000010(n) = eulerphi(n);
A046523(n) = { my(f=vecsort(factor(n)[, 2], , 4), p); prod(i=1, #f, (p=nextprime(p+1))^f[i]); };  \\ This function from Charles R Greathouse IV, Aug 17 2011
A286160(n) = (2 + ((A000010(n)+A046523(n))^2) - A000010(n) - 3*A046523(n))/2;
for(n=1, 10000, write("b286160.txt", n, " ", A286160(n)));

from sympy import factorint, totient
def T(n, m): return ((n + m)**2 - n - 3*m + 2)/2
def P(n):
    f = factorint(n)
    return sorted([f[i] for i in f])
def a046523(n):
    x=1
    while True:
        if P(n) == P(x): return x
        else: x+=1
def a(n): return T(totient(n), a046523(n)) # Indranil Ghosh, May 06 2017

(define (A286160 n) (* (/ 1 2) (+ (expt (+ (A000010 n) (A046523 n)) 2) (- (A000010 n)) (- (* 3 (A046523 n))) 2)))

a(n) = (1/2)*(2 + ((A000010(n)+A046523(n))^2) - A000010(n) - 3*A046523(n)).

A233544 Number of ways to write n = k^2 + m with k > 0 and m >= k^2 such that sigma(k^2) + phi(m) is prime, where sigma(k^2) is the sum of all (positive) divisors of k^2, and phi(.) is Euler's totient function (A000010).

Original entry on oeis.org

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

Offset: 1

Zhi-Wei Sun, Dec 12 2013

nonn

Conjectures:
(i) a(n) > 0 for all n > 1.
(ii) Any integer n > 1 can be written as k + m with k > 0 and m > 0 such that sigma(k)^2 + phi(m) (or sigma(k) + phi(m)^2) is prime.
Part (i) of the conjecture is stronger than the conjecture in A232270. We have verified it for n up to 10^8.
I verified the conjecture to 3*10^9. The conjecture is almost surely true. - Charles R Greathouse IV, Dec 13 2013
There are no counterexamples to conjecture (i) < 5.12 * 10^10. - Jud McCranie, Jul 23 2017
The conjectures appeared as Conjecture 3.31 in the linked 2017 paper. - Zhi-Wei Sun, Nov 30 2018

			a(10) = 1 since 10 = 1^2 + 9 with sigma(1^2) + phi(9) = 1 + 6 = 7 prime.
a(25) = 1 since 25 = 2^2 + 21 with sigma(2^2) + phi(21) = 7 + 12 = 19 prime.
a(34) = 1 since 34 = 4^2 + 18 with sigma(4^2) + phi(18) = 31 + 6 = 37 prime.
a(46) = 1 since 46 = 2^2 + 42 with sigma(2^2) + phi(42) = 7 + 12 = 19 prime.
a(106) = 1 since 106 = 3^2 + 97 with sigma(3^2) + phi(97) = 13 + 96 = 109 prime.
a(163) = 1 since 163 = 3^2 + 154 with sigma(3^2) + phi(154) = 13 + 60 = 73 prime.
a(265) = 1 since 265 = 11^2 + 144 with sigma(11^2) + phi(144) = 133 + 48 = 181 prime.
a(1789) = 1 since 1789 = 1^2 + 1788 with sigma(1^2) + phi(1788) = 1 + 592 = 593 prime.
a(1157) = 3, since 1157 = 10^2 + 1057 with sigma(10^2) + phi(1057) = 217 + 900 = 1117 prime, 1157 = 21^2 + 716 with sigma(21^2) + phi(716) = 741 + 356 = 1097 prime, and 1157 = 24^2 + 581 with sigma(24^2) + phi(581) = 1651 + 492 = 2143 prime. In this example, none of 10, 21 and 24 is a prime power.

Zhi-Wei Sun, Table of n, a(n) for n = 1..10000
Zhi-Wei Sun, Problems on combinatorial properties of primes, arXiv:1402.6641 [math.NT], 2014.
Zhi-Wei Sun, Conjectures on representations involving primes, in: M. Nathanson (ed.), Combinatorial and Additive Number Theory II, Springer Proc. in Math. & Stat., Vol. 220, Springer, Cham, 2017, pp. 279-310. (See also arXiv:1211.1588 [math.NT], 2012-2017.)

Cf. A000010, A000040, A000203, A000290, A220272, A232270, A230494.

sigma[n_]:=Sum[If[Mod[n,d]==0,d,0],{d,1,n}]
a[n_]:=Sum[If[PrimeQ[sigma[k^2]+EulerPhi[n-k^2]],1,0],{k,1,Sqrt[n/2]}]
Table[a[n],{n,1,100}]

a(n)=sum(k=1,sqrtint(n\2),isprime(sigma(k^2)+eulerphi(n-k^2))) \\ Charles R Greathouse IV, Dec 12 2013

A295501 a(n) = phi(4^n-1), where phi is Euler's totient function (A000010).

Original entry on oeis.org

2, 8, 36, 128, 600, 1728, 10584, 32768, 139968, 480000, 2640704, 6635520, 44717400, 132765696, 534600000, 2147483648, 11452896600, 26121388032, 183250539864, 473702400000, 2427720325632, 8834232287232, 45914084232320, 109586090557440, 656100000000000

Offset: 1

Seiichi Manyama, Nov 22 2017

nonn

Max Alekseyev, Table of n, a(n) for n = 1..1128
Eric Weisstein's World of Mathematics, Totient Function.
Wikipedia, Euler's totient function.

Cf. A000010, A053285.
phi(k^n-1): A053287 (k=2), A295500 (k=3), this sequence (k=4), A295502 (k=5), A366623 (k=6), A366635 (k=7), A366654 (k=8), A366663 (k=9), A295503 (k=10), A366685 (k=11), A366711 (k=12).
Cf. A366602, A366603, A366604, A366608.

EulerPhi[4^Range[30] - 1] (* Paolo Xausa, Jun 17 2024 *)

PARI
```
{a(n) = eulerphi(4^n-1)}
```

a(n) = n*A027695(n).

a(n) = A053287(2*n) = A053285(n) * A053287(n). - Max Alekseyev, Jan 07 2024

A326835 Numbers whose divisors have distinct values of the Euler totient function (A000010).

Original entry on oeis.org

1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99, 101, 103, 105, 107, 109, 111, 113, 115, 117, 119, 121, 123, 125, 127

Offset: 1

Amiram Eldar, Oct 28 2019

nonn

Since Sum_{d|k} phi(d) = k, these are numbers k such that the set {phi(d) | d|k} is a partition of k into distinct parts.
Includes all the odd prime numbers, since an odd prime p has 2 divisors, 1 and p, whose phi values are 1 and p-1.
If k is a term, then all the divisors of k are also terms. If k is not a term, then all its multiples are not terms. The primitive terms of the complementary sequence are 2, 63, 273, 513, 585, 825, 2107, 2109, 2255, 3069, ....
In particular, all the terms are odd since 2 is not a term (phi(1) = phi(2)).
The number of terms below 10^k for k = 1, 2, ... are 5, 49, 488, 4860, 48598, 485807, 4857394, 48572251, 485716764, 4857144075, ...
Apparently the sequence has an asymptotic density of 0.4857...

			3 is a term since it has 2 divisors, 1 and 3, and phi(1) = 1 != phi(3) = 2.
15 is a term since the phi values of its divisors, {1, 3, 5, 15}, are distinct: {1, 2, 4, 8}.

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

Cf. A000005, A000010, A032741, A102190, A319695, A319696.

filter:= proc(n) local D;
  D:=numtheory:-divisors(n);
  nops(D) = nops(map(numtheory:-phi,D))
end proc:
select(filter, [seq(i,i=1..200,2)]); # Robert Israel, Oct 29 2019

aQ[n_] := Length @ Union[EulerPhi /@ (d = Divisors[n])] == Length[d];  Select[Range[130], aQ]

isok(k) = #Set(apply(x->eulerphi(x), divisors(k))) == numdiv(k); \\ Michel Marcus, Oct 28 2019

Numbers k such that A319696(k) = A000005(k).
Numbers k such that A319695(k) = A032741(k).
Numbers k such that the k-th row of A102190 has distinct terms.

A033631 Numbers k such that sigma(phi(k)) = sigma(k) where sigma is the sum of divisors function A000203 and phi is the Euler totient function A000010.

Original entry on oeis.org

1, 87, 362, 1257, 1798, 5002, 9374, 21982, 22436, 25978, 35306, 38372, 41559, 50398, 51706, 53098, 53314, 56679, 65307, 68037, 89067, 108946, 116619, 124677, 131882, 136551, 136762, 138975, 144014, 160629, 165554, 170037, 186231, 192394, 197806

Offset: 1

Jud McCranie

nonn

For corresponding values of phi(k) and sigma(k), see A115619 and A115620.
This sequence is infinite because for each positive integer k, 3^k*7*1979 and 3^k*7*2699 are in the sequence (the proof is easy). A108510 gives primes p like 1979 and 2699 such that for each positive integer k, 3^k*7*p is in this sequence. - Farideh Firoozbakht, Jun 07 2005
There is another class of [conjecturally] infinite subsets connected to A005385 (safe primes). Examples: Let s,t be safe primes, s<>t, then 3^2*5*251*s, 2^2*61*71*s, 2*61*s*t and 2*19*311*s are in this sequence. So is 3*s*A108510(m). (There are some obvious exceptions for small s, t.) - Vim Wenders, Dec 27 2006

J.-M. De Koninck, Ces nombres qui nous fascinent, Entry 87, p. 29, Ellipses, Paris 2008.
R. K. Guy, Unsolved Problems in Number Theory, B42.
D. Wells, The Penguin Dictionary of Curious and Interesting Numbers, Penguin Books 1997.
David Wells, Curious and Interesting Numbers (Revised), Penguin Books, page 114.

T. D. Noe, Table of n, a(n) for n = 1..1000
J.-M. De Koninck, F. Luca, Positive integers n such that sigma(phi(n))=sigma(n), JIS 11 (2008) 08.1.5.
S. W. Golomb, Equality among number-theoretic functions, Unpublished manuscript. (Annotated scanned copy)

Cf. A000203, A000010, A006872, A115619, A115620.

[k:k in [1..200000]| DivisorSigma(1,EulerPhi(k)) eq DivisorSigma(1,k)]; // Marius A. Burtea, Feb 09 2020

Do[If[DivisorSigma[1, EulerPhi[n]]==DivisorSigma[1, n], Print[n]], {n, 1, 10^5}]

is(n)=sigma(eulerphi(n))==sigma(n) \\ Charles R Greathouse IV, Feb 13 2013

Entry revised by N. J. A. Sloane, Apr 10 2006

A037171 Numbers n such that phi(n) = pi(n), i.e., A000010(n) = A000720(n).

Original entry on oeis.org

2, 3, 4, 8, 10, 14, 20, 90

Offset: 1

Naohiro Nomoto

David W. Wilson and Jeffrey Shallit showed that 90 is the last term.
Leo Moser proved in 1951 that these are the only terms, but he missed the term 10. - Amiram Eldar, May 15 2017
phi(n) >= pi(n) for n >= 61, and phi(n) > pi(n) for n > 90. - Jonathan Sondow, Dec 02 2017

			phi(10)=4, pi(10)=4.
a(1)=2 since k=2 is the lowest index for which A000720(n) = A000010(n), i.e., EulerPhi(n) = PrimePi(n). - _M. F. Hasler_, Mar 30 2007

P. Birch and D. Singmaster, An elementary number theory result, Math. Soc. Newsl., 12 (1984), 10-13.
D. S. Mitrinovic et al., Handbook of Number Theory, Kluwer, p. 11.

Leo Moser, On the equation ϕ(n) = π(n), Pi Mu Epsilon Journal. Vol. 1, No. 5 (1951), pp. 177-180.

Cf. A000010, A000720, A037228, A037230.

select(x->numtheory[phi](x)=numtheory[pi](x),[$1..999]); # M. F. Hasler, Mar 30 2007

for(n=1,1e5,if(primepi(n)==eulerphi(n),print(n))) /* M. F. Hasler, Mar 30 2007 */

A037228(a(n)) = 0. - Jonathan Sondow, Dec 02 2017

A049690 a(n) = Sum_{k=1..n} phi(2*k), where phi = Euler totient function, cf. A000010.

Original entry on oeis.org

0, 1, 3, 5, 9, 13, 17, 23, 31, 37, 45, 55, 63, 75, 87, 95, 111, 127, 139, 157, 173, 185, 205, 227, 243, 263, 287, 305, 329, 357, 373, 403, 435, 455, 487, 511, 535, 571, 607, 631, 663, 703, 727, 769, 809, 833, 877, 923, 955, 997, 1037, 1069, 1117, 1169, 1205

Offset: 0

Clark Kimberling

nonn

Nathaniel Johnston, Table of n, a(n) for n = 0..10000

a(n)=b(2n), where b=A049689. Bisections: A099958, A190815.

Cf. A062570.

A049690 := proc(n) return add(numtheory[phi](2*k), k=1..n): end: seq(A049690(n),n=0..54); # Nathaniel Johnston, May 24 2011

A049690[0]:=0; A049690[n_]:=A049690[n-1]+EulerPhi[2n]; Array[A049690,200,0] (* Enrique Pérez Herrero, Feb 25 2012 *)

a(n)=sum(k=1,n,eulerphi(2*k)) \\ Charles R Greathouse IV, Feb 19 2013

from sympy import totient
def A049690(n): return sum(totient(n) for n in range(1,n+1,2)) + (sum(totient(n) for n in range(2,n+1,2))<<1) # Chai Wah Wu, Aug 04 2024

# faster program using program from A002088 and recursive formula
def A049690(n): return A002088(n) + A049690(n>>1) if n else 0 # Chai Wah Wu, Aug 04 2024

a(n) ~ 4*n^2/Pi^2. - Vaclav Kotesovec, Aug 20 2021

a(n) = A002088(n) + a(floor(n/2)). - Chai Wah Wu, Aug 04 2024

More terms from Vladeta Jovovic, May 18 2001

A366623 a(n) = phi(6^n-1), where phi is Euler's totient function (A000010).

Original entry on oeis.org

4, 24, 168, 864, 6200, 30240, 223944, 1119744, 7457184, 37200000, 277618528, 1254113280, 10445497920, 51618196224, 365601600000, 1770091315200, 13439285266176, 62336092492800, 484935499902880, 2179146240000000, 17141125020596640, 86330728271779200

Offset: 1

Sean A. Irvine, Oct 14 2023

nonn

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

phi(k^n-1): A053287 (k=2), A295500 (k=3), A295501 (k=4), A295502 (k=5), this sequence (k=6), A366635 (k=7), A366654 (k=8), A366663 (k=9), A295503 (k=10), A366685 (k=11), A366711 (k=12).

Cf. A024062, A000010, A295502, A366620, A366621, A366622.

EulerPhi[6^Range[22] - 1] (* Paul F. Marrero Romero, Oct 23 2023 *)

PARI
```
{a(n) = eulerphi(6^n-1)}
```

a(n) = A000010(A024062(n)). - Paul F. Marrero Romero, Oct 23 2023

A366685 a(n) = phi(11^n-1), where phi is Euler's totient function (A000010).

Original entry on oeis.org

4, 32, 432, 3840, 64400, 373248, 7613424, 56217600, 765889344, 6913984000, 114117380608, 599824465920, 13796450740800, 98909341090560, 1356399209088000, 11341872916070400, 202178811399717504, 1171410130065973248, 24463636179365818512, 176391086415667200000

Offset: 1

Sean A. Irvine, Oct 16 2023

nonn

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

phi(k^n-1): A053287 (k=2), A295500 (k=3), A295501 (k=4), A295502 (k=5), A366623 (k=6), A366635 (k=7), A366654 (k=8), A366663 (k=9), A295503 (k=10), this sequence (k=11), A366711 (k=12).

Cf. A000010, A024127, A366681, A366682, A366683, A366684.

Mathematica
```
EulerPhi[11^Range[30] - 1]
```
PARI
```
{a(n) = eulerphi(11^n-1)}
```

cp's OEIS Frontend

A203966 Numbers n such that phi(n) divides n+1, where phi is Euler's totient function (A000010).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A286160 Compound filter: a(n) = T(A000010(n), A046523(n)), where T(n,k) is sequence A000027 used as a pairing function.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Python

Scheme

Formula

A233544 Number of ways to write n = k^2 + m with k > 0 and m >= k^2 such that sigma(k^2) + phi(m) is prime, where sigma(k^2) is the sum of all (positive) divisors of k^2, and phi(.) is Euler's totient function (A000010).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A295501 a(n) = phi(4^n-1), where phi is Euler's totient function (A000010).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A326835 Numbers whose divisors have distinct values of the Euler totient function (A000010).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A033631 Numbers k such that sigma(phi(k)) = sigma(k) where sigma is the sum of divisors function A000203 and phi is the Euler totient function A000010.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Extensions

A037171 Numbers n such that phi(n) = pi(n), i.e., A000010(n) = A000720(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs