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
\$\endgroup\$
1

7 Answers 7

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
\$\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.

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

Charcoal, 44 25 bytes

crossed out 44 is still regular 44

I№EX⊕θ²LΦ⊕ι⬤…·²λ∨﹪λν﹪ιν⊕θ

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
   X                        Raised to power
      ²                     Literal integer `2`
  E                         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
       L                    Take the length
 №                          Count occurences of
                        θ   Input `n`
                       ⊕    Incremented
I                           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.

\$\endgroup\$
2
  • \$\begingroup\$ Can you use the upper bounds \$(n+1)^2\$, or \$2n^2\$? \$\endgroup\$ 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\$
    – Neil
    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

\$\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!

\$\endgroup\$
1
  • 2
    \$\begingroup\$ -1 byte with n*n*3->2<<n \$\endgroup\$
    – AnttiP
    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!

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.