12
\$\begingroup\$

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
Improve this question
\$\endgroup\$
1
  • \$\begingroup\$ Related \$\endgroup\$ Commented Dec 18, 2021 at 18:26

7 Answers 7

Reset to default
6
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
4
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ By borrowing the totient calculation from this tip from Lynn, you can do 73 bytes \$\endgroup\$ Commented Dec 19, 2021 at 0:32
3
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Can you use the upper bounds \$(n+1)^2\$, or \$2n^2\$? \$\endgroup\$ Commented Dec 18, 2021 at 22:56
  • \$\begingroup\$ @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. \$\endgroup\$ Commented Dec 18, 2021 at 23:54
3
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
2
2
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
1
  • 2
    \$\begingroup\$ -1 byte with n*n*3->2<<n \$\endgroup\$ Commented Dec 18, 2021 at 20:02
1
\$\begingroup\$

Pari/GP, 32 bytes

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

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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)
Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.