A000010 -id:A000010 - cp's OEIS frontend

A290077 a(n) = A000010(A005940(1+n)).

1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 8, 4, 20, 6, 18, 8, 10, 6, 12, 8, 24, 8, 24, 8, 42, 20, 40, 12, 100, 18, 54, 16, 12, 10, 20, 12, 40, 12, 36, 16, 60, 24, 48, 16, 120, 24, 72, 16, 110, 42, 84, 40, 168, 40, 120, 24, 294, 100, 200, 36, 500, 54, 162, 32, 16, 12, 24, 20, 48, 20, 60, 24, 72, 40, 80, 24, 200, 36, 108, 32, 120, 60, 120

Offset: 0

Antti Karttunen, Jul 19 2017

nonn

Each n occurs A014197(n) times in total in this sequence.

Antti Karttunen, Table of n, a(n) for n = 0..16384
Index entries for sequences related to binary expansion of n

Cf. A000010, A000040, A005940, A014197, A290076, A323915, A324052, A324054, A364568.

f[n_, i_, x_]:=f[n, i, x]=Which[n==0, x, EvenQ[n], f[n/2, i + 1, x], f[(n - 1)/2, i, x Prime[i]]]; a005940[n_]:=f[n - 1, 1, 1]; Table[EulerPhi[a005940[n + 1]], {n, 0, 100}] (* Indranil Ghosh, Jul 20 2017 *)

A005940(n) = { my(p=2, t=1); n--; until(!n\=2, if((n%2), (t*=p), p=nextprime(p+1))); t };
A290077(n) = eulerphi(A005940(1+n));

A290077(n) = { my(p=2,z=1); while(n, if(!(n%2), p=nextprime(1+p), z *= (p-(1==(n%4)))); n>>=1); (z); }; \\ Antti Karttunen, Aug 05 2023

def A290077(n):
    i = 1
    m = 1
    while n > 0:
      if 0==(n%2):
        n = n//2
        i += 1
      else:
        if(1==(n%4)):
          n = (n-1)//4
          m *= sloane.A000040(i)-1
          i += 1
        else:
          n = (n-1)//2
          m *= sloane.A000040(i)
    return m

(define (A290077 n) (A000010 (A005940 (+ 1 n))))

(define (A290077 n) (let loop ((n n) (m 1) (i 1)) (cond ((zero? n) m) ((even? n) (loop (/ n 2) m (+ 1 i))) ((= 1 (modulo n 4)) (loop (/ (- n 1) 4) (* m (- (A000040 i) 1)) (+ 1 i))) (else (loop (/ (- n 1) 2) (* m (A000040 i)) i))))) ;; Requires only an implementation of A000040, see for example under A083221.

a(n) = A000010(A005940(1+n)).

A319696 Number of distinct values obtained when Euler phi (A000010) is applied to the divisors of n.

Original entry on oeis.org

1, 1, 2, 2, 2, 2, 2, 3, 3, 2, 2, 3, 2, 2, 4, 4, 2, 3, 2, 4, 4, 2, 2, 4, 3, 2, 4, 4, 2, 4, 2, 5, 4, 2, 4, 5, 2, 2, 4, 5, 2, 4, 2, 4, 6, 2, 2, 5, 3, 3, 4, 4, 2, 4, 4, 6, 4, 2, 2, 5, 2, 2, 5, 6, 4, 4, 2, 4, 4, 4, 2, 7, 2, 2, 6, 4, 4, 4, 2, 6, 5, 2, 2, 6, 4, 2, 4, 6, 2, 6, 4, 4, 4, 2, 4, 6, 2, 3, 6, 6, 2, 4, 2, 6, 8

Offset: 1

Antti Karttunen, Oct 02 2018

nonn

			For n = 6, it has four divisors: 1, 2, 3 and 6, and applying A000010 to these gives 1, 1, 2, 2, with just two distinct values, thus a(6) = 2.

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

Cf. A000010, A319695.

Cf. also A184395, A319686.

A319696(n) = { my(m=Map(),s,k=0); fordiv(n,d,if(!mapisdefined(m,s=eulerphi(d)), mapput(m,s,s); k++)); (k); };

a(n) = A319695(n) + [n (mod 4) != 2], where [ ] is the Iverson bracket, resulting 0 when n = 2 mod 4, and 1 otherwise.

A320778 Inverse Euler transform of the Euler totient function phi = A000010.

Original entry on oeis.org

1, 1, 0, 1, 0, 2, -3, 4, -4, 4, -9, 14, -19, 30, -42, 50, -76, 128, -194, 286, -412, 598, -909, 1386, -2100, 3178, -4763, 7122, -10758, 16414, -25061, 38056, -57643, 87568, -133436, 203618, -311128, 475536, -726355, 1109718, -1697766, 2601166, -3987903, 6114666

Offset: 0

Gus Wiseman, Oct 22 2018

sign

The Euler transform of a sequence q is the sequence of coefficients of x^n, n > 0, in the expansion of Product_{n > 0} 1/(1 - x^n)^q(n). The constant term 1 is sometimes taken to be the zeroth part of the Euler transform.

Number theoretical functions: A000005, A000010, A000203, A001055, A001221, A001222, A008683, A010054.
Euler transforms: A000081, A001970, A006171, A007294, A061255, A061256, A061257, A073576, A117209, A293548, A293549.
Inverse Euler transforms: A059966, A320767, A320776, A320777, A320779, A320780, A320781, A320782.

# The function EulerInvTransform is defined in A358451.
a := EulerInvTransform(n -> ifelse(n=0, 1, NumberTheory:-Totient(n))):
seq(a(n), n = 0..43); # Peter Luschny, Nov 21 2022

EulerInvTransform[{}]={};EulerInvTransform[seq_]:=Module[{final={}},For[i=1,i<=Length[seq],i++,AppendTo[final,i*seq[[i]]-Sum[final[[d]]*seq[[i-d]],{d,i-1}]]];
Table[Sum[MoebiusMu[i/d]*final[[d]],{d,Divisors[i]}]/i,{i,Length[seq]}]];
EulerInvTransform[Array[EulerPhi,30]]

A366618 a(n) = phi(5^n+1), where phi is Euler's totient function (A000010).

Original entry on oeis.org

1, 2, 12, 36, 312, 1040, 7200, 25088, 183808, 557928, 4396800, 15333120, 121680000, 406812744, 2817007200, 8558784000, 76264519680, 254230063200, 1710194342400, 6349120596480, 47334145996800, 127169887444992, 1088029470747648, 3889097389599864

Offset: 0

Sean A. Irvine, Oct 14 2023

nonn

Max Alekseyev, Table of n, a(n) for n = 0..471

Cf. A000010, A034474, A057939, A074478, A295502, A366615, A366616, A366617.

Cf. A053285, A366579, A366608, A366630, A366639, A366658, A366667, A366669, A366690, A366716.

EulerPhi[5^Range[0,30]+1] (* Harvey P. Dale, Jun 07 2025 *)

PARI
```
{a(n) = eulerphi(5^n+1)}
```

A366639 a(n) = phi(7^n+1), where phi is Euler's totient function (A000010).

Original entry on oeis.org

1, 4, 20, 168, 1200, 7600, 43200, 407680, 2712832, 19707408, 112560000, 945677920, 6768230400, 47530457728, 271289229120, 2096760960000, 16569393144832, 116315256993600, 597938524646400, 5699431359135360, 38890647857280000, 270061302781670400

Offset: 0

Sean A. Irvine, Oct 15 2023

nonn

Max Alekseyev, Table of n, a(n) for n = 0..387

Cf. A034491, A000010, A057937, A227575, A366635, A366636, A366637, A366638.

Cf. A053285, A366579, A366608, A366618, A366630, A366658, A366667, A366669, A366690, A366716.

EulerPhi[7^Range[0,21] + 1] (* Paul F. Marrero Romero, Nov 05 2023 *)

PARI
```
{a(n) = eulerphi(7^n+1)}
```

a(n) = A000010(A034491(n)). - Paul F. Marrero Romero, Nov 06 2023

A366658 a(n) = phi(8^n+1), where phi is Euler's totient function (A000010).

Original entry on oeis.org

1, 6, 48, 324, 3840, 19800, 186624, 1365336, 16515072, 84768120, 760320000, 5632621632, 64258375680, 366369658200, 3105655160832, 20140520400000, 280012271910912, 1495522910085120, 12824556668190720, 95907982079387520, 1080582572777472000, 5688765822212629632

Offset: 0

Sean A. Irvine, Oct 15 2023

nonn

Max Alekseyev, Table of n, a(n) for n = 0..502

Cf. A062395, A000010, A057936, A274905, A366654, A366655, A366656, A366657, A366671.

Cf. A053285, A366579, A366608, A366618, A366630, A366639, A366667, A366669, A366690, A366716.

EulerPhi[8^Range[0, 21] + 1] (* Paul F. Marrero Romero, Oct 17 2023 *)

PARI
```
{a(n) = eulerphi(8^n+1)}
```

from sympy import totient
def A366658(n): return totient((1<<3*n)+1) # Chai Wah Wu, Oct 15 2023

a(n) = A000010(A062395(n)). - Paul F. Marrero Romero, Nov 06 2023

a(n) = A053285(3*n). - Max Alekseyev, Jan 09 2024

A053574 Exponent of 2 in phi(n) where phi(n) = A000010(n).

Original entry on oeis.org

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

Offset: 1

Labos Elemer, Jan 18 2000

			For n = 513 = 27*19, phi(513) = 4*81 so exponent of 2 is 2, thus a(513) = 2.

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

Cf. A000010, A007814, A053575, A286572.

IntegerExponent[Array[EulerPhi, 120], 2] (* Michael De Vlieger, Aug 16 2017 *)

vector(66,n,valuation(eulerphi(n),2)) \\ Joerg Arndt, Apr 22 2011

a(n) = A007814(A000010(n)).
A000010(n) = A053575(n) * 2^a(n). - Antti Karttunen, May 26 2017
Additive with a(2^e) = e-1, and a(p^e) = A007814(p-1) for an odd prime p. - Amiram Eldar, Sep 05 2023

Data section extended to 120 terms by Antti Karttunen, May 26 2017

A058339 Number of solutions to 1 + phi(x) = prime(n), where phi is A000010.

Original entry on oeis.org

2, 3, 4, 4, 2, 6, 6, 4, 2, 2, 2, 8, 9, 4, 2, 2, 2, 9, 2, 2, 17, 2, 2, 6, 17, 4, 2, 2, 9, 6, 2, 2, 2, 2, 2, 2, 7, 4, 2, 2, 2, 10, 2, 21, 2, 2, 2, 2, 2, 2, 6, 2, 31, 2, 10, 2, 2, 2, 9, 8, 2, 2, 2, 2, 16, 2, 2, 18, 2, 6, 12, 2, 2, 2, 2, 2, 2, 13, 13, 6, 2, 13, 2, 34

Offset: 1

Labos Elemer, Dec 14 2000

nonn

			The equation phi(x) = p-1 always has at least 2 solutions: p and 2p a prime and a composite. Many times more than 2 x gives phi(x) = p-1. For p-1 = 96 there are 17 (that is, an odd number of) solutions: {97, 119, 153, 194, 195, 208, 224, 238, 260, 280, 288, 306, 312, 336, 360, 390, 420}, 4 odd and 13 even numbers while for p-1 = 100 there are 4 (an even number of) solutions: {101, 125, 202, 250}. For all odd solutions x, 2x is also a solution.
1+phi(x) = 11 has 2 solutions: 11 and 22; 1+phi(x) = 241 has 31 solutions: x = {241, 287, 305, 325, 369, 385, 429, 465, 482, 488, 495, 496, 525, 572, 574, 610, 616, 620, 650, 700, 732, 738, 744, 770, 792, 858, 900, 924, 930, 990, 1050}.

T. D. Noe, Table of n, a(n) for n = 1..10000
Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).
David M. Bressoud, CNT.m, Computational Number Theory Mathematica package.

Cf. A000010, A000040, A006093, A058340, A066071, A066072, A066073, A066074, A066075, A066076, A066077, A066080.

with(numtheory): >[seq(nops(invphi(-1+ithprime(i))),i=1..256)];

Needs["CNT`"]; Table[Length[PhiInverse[Prime[n] - 1]], {n, 100}] (* T. D. Noe, Dec 11 2013 *)
Take[Length /@ Values@ KeySelect[KeyMap[# + 1 &, PositionIndex@ Array[EulerPhi, 10^4]], PrimeQ], 84] (* Michael De Vlieger, Dec 29 2017 *)

a(n) = invphiNum(prime(n) - 1); \\ Amiram Eldar, Aug 18 2024, using Max Alekseyev's invphi.gp

a(n) = A210500(n) + A210501(n). - Arkadiusz Wesolowski, Jan 19 2013

Offset corrected by Arkadiusz Wesolowski, Jan 19 2013

A122254 Numbers with 3-smooth Euler's totient (A000010).

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 24, 26, 27, 28, 30, 32, 34, 35, 36, 37, 38, 39, 40, 42, 45, 48, 51, 52, 54, 56, 57, 60, 63, 64, 65, 68, 70, 72, 73, 74, 76, 78, 80, 81, 84, 85, 90, 91, 95, 96, 97, 102, 104, 105, 108, 109, 111, 112, 114

Offset: 1

Reinhard Zumkeller, Aug 29 2006

An integer n>=3 belongs to this sequence if and only if a regular n-gon can be constructed using straightedge and conic sections (details in Gibbins and Smolinsky, see below). - Austin Shapiro, Nov 14 2021

Products of 3-smooth numbers (A003586) and squarefree numbers whose prime factors are all Pierpont primes (A005109). - Amiram Eldar, Dec 03 2022

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Aliska Gibbins and Lawrence Smolinsky, Geometric Constructions with Ellipses, The Mathematical Intelligencer 31(1) (2009), 57-62.

Cf. A000010, A003586 (3-smooth), A005109.

Subsequence of A122260.

Select[Range@115, Max[FactorInteger[EulerPhi[#]][[All, 1]]] < 5 &] (* Ivan Neretin, Jul 28 2015 *)

is(n)=n=eulerphi(n);n>>=valuation(n,2);n==3^valuation(n,3) \\ Charles R Greathouse IV, Feb 21 2013

list(lim)=my(v=List(),u,t);for(i=0,log(lim--+1.5)\log(3),t=3^i;while(t<=lim,if(isprime(t+1),listput(v,t+1));t<<=1));v=vecsort(Vec(v));u=List([1]);for(i=3,#v,for(j=1,#u,t=v[i]*u[j];if(t>lim,next(2));listput(u,t)));u=vecsort(Vec(u));v=List(u);for(i=1,#u,t=u[i];while((t*=3)<=lim,listput(v,t)));u=Vec(v);v=List(u);for(i=1,#u,t=u[i];while((t<<=1)<=lim,listput(v,t)));vecsort(Vec(v)) \\ Charles R Greathouse IV, Feb 22 2013

from itertools import count, islice
from sympy import multiplicity, factorint
def A065333(n): return int(3**(multiplicity(3,m:=n>>(~n&n-1).bit_length()))==m)
def A122254_gen(startvalue=1): # generator of terms >= startvalue
    return filter(lambda n:all(p<=3 or (e==1 and A065333(p-1)) for p,e in factorint(n).items()), count(max(startvalue,1)))
A122254_list = list(islice(A122254_gen(),40)) # Chai Wah Wu, Dec 20 2024

a(n) = A048135(n-2) for n>2.
a(n) = A122260(n) = A048737(n) for n < 22.
Sum_{n>=1} 1/a(n) = 3 * Product_{p > 3 in A005109} (1 + 1/p) = 5.38288865867495675807... . - Amiram Eldar, Dec 03 2022

A159929 INVERT transform of phi(n), A000010.

Original entry on oeis.org

1, 1, 2, 5, 11, 26, 57, 131, 296, 669, 1515, 3430, 7765, 17577, 39790, 90069, 203897, 461562, 1044847, 2365239, 5354224, 12120455, 27437267, 62110208, 140599921, 318278385, 720492104, 1630990029, 3692099407, 8357867190, 18919843773, 42829166807, 96953101328, 219474357191, 496827773575

Offset: 0

Gary W. Adamson, Apr 26 2009

nonn

Number of compositions of n into parts where there are phi(k) sorts of part k. - Joerg Arndt, Sep 30 2012

			a(6) = 57 = (1, 1, 2, 2, 4, 2) dot (26, 11, 5, 2, 1, 1) = (26 + 11 + 10 + 4 + 4 + 2).

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Cf. A000010.

Row sums of A340995.

a:= proc(n) option remember; `if`(n=0, 1,
      add(a(n-i)*numtheory[phi](i), i=1..n))
    end:
seq(a(n), n=0..35);  # Alois P. Heinz, Sep 22 2017

a[n_] := a[n] = If[n == 0, 1, Sum[a[n-i] EulerPhi[i], {i, 1, n}]];
a /@ Range[0, 35] (* Jean-François Alcover, Oct 31 2020, after Maple *)

N=66;  x='x+O('x^N);
Vec( 1/( 1 - sum(k=1,N, eulerphi(k)*x^k ) ) - 1 )
/* Joerg Arndt, Sep 30 2012 */

INVERT transform of A000010.
G.f.: 1/( 1 - Sum_{k>=1} phi(k) * x^k ) where phi = A000010. Joerg Arndt, Sep 30 2012
a(n) ~ c * d^n, where d = 2.26371672715382105671101924573765243871241560288177676216035633730282369149... is the root of the equation Sum_{k>=1} phi(k)/d^k = 1 and c = 0.42880036544961338799475947921442516792321060146527623589359809145075482942... - Vaclav Kotesovec, Aug 18 2021

a(0)=1 prepended by Alois P. Heinz, Sep 22 2017

cp's OEIS Frontend

A290077 a(n) = A000010(A005940(1+n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Sage

Scheme

Scheme

Formula

A319696 Number of distinct values obtained when Euler phi (A000010) is applied to the divisors of n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A320778 Inverse Euler transform of the Euler totient function phi = A000010.

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

Mathematica

A366618 a(n) = phi(5^n+1), where phi is Euler's totient function (A000010).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

A366639 a(n) = phi(7^n+1), where phi is Euler's totient function (A000010).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A366658 a(n) = phi(8^n+1), where phi is Euler's totient function (A000010).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A053574 Exponent of 2 in phi(n) where phi(n) = A000010(n).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A058339 Number of solutions to 1 + phi(x) = prime(n), where phi is A000010.

Views

Author