Multiplicity of Shared Totients

Question

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 sequence 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 code-golf, 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

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

Haskell, 61 55 bytes

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

Answer 5

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!

Answer 6

Pari/GP, 32 bytes

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

Try it online!

Answer 7

05AB1E, 6 bytes

>nLÕI¢

Port of @hyper-neutrino♦'s Jelly answer.

Try it online or verify the first 25 terms.

Explanation:

>       # Increase the (implicit) input by 1
 n      # Square it
  L     # Pop and push a list in the range [1,(input+1)²]
   Õ    # Convert each value in this list to its Euler's Totient
    I¢  # Count how many times the input is in this list
        # (after which the result is output implicitly)