# Multiplicity of Shared Totients

Euler's totient function, $$\\varphi(n)\$$, counts the number of integers $$\1 \le k \le n\$$ such that $$\\gcd(k, n) = 1\$$. For example, $$\\varphi(9) = 6\$$ as $$\1,2,4,5,7,8\$$ are all coprime to $$\9\$$. However, $$\\varphi(n)\$$ is not injective, meaning that there are distinct integers $$\m, n\$$ such that $$\\varphi(m) = \varphi(n)\$$. For example, $$\\varphi(7) = \varphi(9) = 6\$$.

The number of integers $$\n\$$ such that $$\\varphi(n) = k\$$, for each positive integer $$\k\$$, is given by A014197. To clarify this, consider the table

$$\k\$$ Integers $$\n\$$ such that $$\\varphi(n) = k\$$ How many? (aka A014197)
$$\1\$$ $$\1, 2\$$ $$\2\$$
$$\2\$$ $$\3, 4, 6\$$ $$\3\$$
$$\3\$$ $$\\$$ $$\0\$$
$$\4\$$ $$\5, 8, 10, 12\$$ $$\4\$$
$$\5\$$ $$\\$$ $$\0\$$
$$\6\$$ $$\7, 9, 14, 18\$$ $$\4\$$
$$\7\$$ $$\\$$ $$\0\$$
$$\8\$$ $$\15, 16, 20, 24, 30\$$ $$\5\$$
$$\9\$$ $$\\$$ $$\0\$$
$$\10\$$ $$\11, 22\$$ $$\2\$$

You are to implement A014197.

This is a standard challenge. You may choose to do one of these three options:

• Take a positive integer $$\k\$$, and output the $$\k\$$th integer in the sequence (i.e. the number of integers $$\n\$$ such that $$\\varphi(n) = k\$$). Note that, due to this definition, you may not use 0 indexing.
• Take a positive integer $$\k\$$ and output the first $$\k\$$ integers in the sequence
• Output the entire sequence, in order, indefinitely

This is , so the shortest code in bytes wins.

The first 92 elements in the sequence are

2,3,0,4,0,4,0,5,0,2,0,6,0,0,0,6,0,4,0,5,0,2,0,10,0,0,0,2,0,2,0,7,0,0,0,8,0,0,0,9,0,4,0,3,0,2,0,11,0,0,0,2,0,2,0,3,0,2,0,9,0,0,0,8,0,2,0,0,0,2,0,17,0,0,0,0,0,2,0,10,0,2,0,6,0,0,0,6,0,0,0,3

• Related Commented Dec 18, 2021 at 18:26

# Jelly, 6 bytes

‘²RÆṪċ


Try It Online!

‘²RÆṪċ  Main Link
‘       x + 1
²      (x + 1) ^ 2
R     range
ÆṪ   totient
ċ  count how many times x shows up


# Python 3, 86 bytes

lambda i:sum(i==sum(2>math.gcd(n,k)for n in range(k))for k in range(3**i))
import math


Try it online!

The 3**i is sufficient. It follows from this inequality.

• By borrowing the totient calculation from this tip from Lynn, you can do 73 bytes
– ovs
Commented Dec 19, 2021 at 0:32

# Charcoal, 44 25 bytes

crossed out 44 is still regular 44

Ｉ№ＥＸ⊕θ²ＬΦ⊕ι⬤…·²λ∨﹪λν﹪ιν⊕θ


Try it online! Link is to verbose version of code. Outputs the nth term of the sequence. Edit: Saved 16 bytes by stealing @HyperNeutrino's upper bound, which then allowed a further 3 bytes of golfing. Explanation:

     θ                      Input n
⊕                       Incremented
Ｘ                        Raised to power
²                     Literal integer 2
Ｅ                         Map over implicit range
ι                 Current value
⊕                  Incremented
Φ                   Filter over implicit range
…·              Inclusive range
²             From literal integer 2
λ            To current value
⬤                All values satisfy
ν        Current value
﹪          Does not divide into
λ         Inner value
∨           Logical Or
ν     Current value
﹪       Does not divide into
ι      Outer value
Ｌ                    Take the length
№                          Count occurences of
θ   Input n
⊕    Incremented
Ｉ                           Cast to string
Implicitly print


The innermost loop erroneously counts 0 as coprime, so this is adjusted for by searching for occurrences of n+1.

• Can you use the upper bounds $(n+1)^2$, or $2n^2$? Commented Dec 18, 2021 at 22:56
• @cairdcoinheringaahing Yeah, I'm pretty sure n²+n+1 is an easier upper bound for the formula I had; 2n² doesn't work for me as Charcoal uses 0-indexing but (n+1)² is fine.
– Neil
Commented Dec 18, 2021 at 23:54

f x=sum[1|z<-[1..2*x^2],sum[1|y<-[1..z],gcd z y==1]==x]


Try it Online!

-6 bytes thanks to Unrelated String

• Commented Dec 20, 2021 at 8:53
• That's a lot shorter, thanks! Commented Dec 20, 2021 at 19:29

# JavaScript (ES6), 88 bytes

n=>eval("for(t=0,j=n*n*3;j--;)t+=(P=k=>k--&&(C=(a,b)=>b?C(b,a%b):a<2)(j,k)+P(k))(j)==n")


Try it online!

• -1 byte with n*n*3->2<<n Commented Dec 18, 2021 at 20:02

# Pari/GP, 32 bytes

n->sum(i=1,2*n^2,eulerphi(i)==n)


Try it online!

# 05AB1E, 6 bytes

>nLÕI¢


>       # Increase the (implicit) input by 1