12
\$\begingroup\$

Related: Iterated phi(n) function.

Your challenge is to compute the iterated phi function:

f(n) = number of iterations of φ for n to reach 1.

Where φ is Euler's totient function.

Related OEIS.

Here's the graph of it:

enter image description here


Rules:

Your goal is to output f(n) from n=2 to n=100.

This is code-golf, so shortest code wins.

Here's the values you can check against:

1, 2, 2, 3, 2, 3, 3, 3, 3, 4, 3, 4, 3, 4, 4, 5, 3, 4, 4, 4, 4, 5, 4, 5, 4, 4, 4, 5, 4, 5, 5, 5, 5, 5, 4, 5, 4, 5, 5, 6, 4, 5, 5, 5, 5, 6, 5, 5, 5, 6, 5, 6, 4, 6, 5, 5, 5, 6, 5, 6, 5, 5, 6, 6, 5, 6, 6, 6, 5, 6, 5, 6, 5, 6, 5, 6, 5, 6, 6, 5, 6, 7, 5, 7, 5, 6, 6, 7, 5, 6, 6, 6, 6, 6, 6, 7, 5, 6, 6
\$\endgroup\$
  • \$\begingroup\$ @LuisMendo Fixed, and also added graph + values to check against. :-) \$\endgroup\$ – Simply Beautiful Art Dec 4 '17 at 16:04
  • 1
    \$\begingroup\$ I've edited in the kolmogorov-complexity tag, as this is essentially outputting a fixed value \$\endgroup\$ – caird coinheringaahing Dec 4 '17 at 16:10
  • 1
    \$\begingroup\$ @SimplyBeautifulArt First prove that there are finitely many values x such that phi(x) is a particular fixed number. \$\endgroup\$ – user202729 Dec 4 '17 at 16:31
  • 2
    \$\begingroup\$ This is a nice challenge, but I think it would be better to just ask for a solution to implement f(n), rather than run it on a range of fixed numbers. This also makes a difference between languages with ability to apply functions on ranges with less bytes (partly chameleon challenge?) \$\endgroup\$ – Uriel Dec 4 '17 at 16:35
  • 1
    \$\begingroup\$ :P Are you implying I should change the challenge to give you an advantage? Regardless of how these rules are stated, some languages will have an advantage and some won't. @Uriel \$\endgroup\$ – Simply Beautiful Art Dec 4 '17 at 16:37

21 Answers 21

10
\$\begingroup\$

Haskell, 53 52 bytes

Thanks nimi for saving 1 byte!

f<$>[2..100]
f 1=0
f n=1+f(sum[1|1<-gcd n<$>[1..n]])

Try it online!

sum[1|1<-gcd n<$>[1..n]] gives φ(n) (Taken from flawr, thanks!)

f is a recursive function that calculates 1+φ(n) if n is not 1, and outputs 0 if n is 1, as there are no more iterations to be taken to reach 1

Finally f<$>[2..100] creates a list of f applied to each element of [2..100]

\$\endgroup\$
7
\$\begingroup\$

Haskell, 70 69 68 bytes

The function (\n->sum[1|1<-gcd n<$>[1..n]]) is the totient function, which we repeatedly apply in the anonymous function. Thanks @laikoni for -1 byte!

EDIT: I just found out @xnor used this exact totient function in a previous challenge.

length.fst.span(>1).iterate(\n->sum[1|1<-gcd n<$>[1..n]])<$>[2..100]

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ This is pretty short for not having a totient builtin! \$\endgroup\$ – Luis Mendo Dec 4 '17 at 16:40
  • 1
    \$\begingroup\$ @LuisMendo H.PWiz found a solution that is even shorter! \$\endgroup\$ – flawr Dec 4 '17 at 17:13
7
\$\begingroup\$

MATL, 16 15 bytes

99:Q"@`_Zptq}x@

Try it online!

Explanation

99:       % Push [1 2 ... 99]
Q         % Add 1 element-wise: gives [2 3 ... 100]
"         % For each k in that array
  @       %   Push k
  `       %   Do...while
    _Zp   %     Euler's totient function
     tq   %     Duplicate, subtract 1. This is the loop condition
  }       %   Finally (execute on loop exit)
  x       %     Delete
  @       %     Push latest k
          %   End (implicit)
          % End (implicit)
          % Display stack (implicit)

Old version, 16 bytes

99:Qt"t_Zp]v&X<q

Try it online!

Explanation

99:       % Push [1 2 ... 99]
Q         % Add 1 element-wise: gives [1 2 ... 100]
t"        % Duplicate. For each (i.e. do the following 100 times)
  t       %   Duplicate
  _Zp     %   Euler's totient function, element-wise
]         % End
v         % Concatenate vertically. Gives a 100×100 matrix
&X<       % Row index of the first minimizing entry for each column.
          % The minimum is guaranteed to be 1, because the number of
          % iterations is more than sufficient.
q         % Subtract 1. Display stack (implicit)
\$\endgroup\$
  • 1
    \$\begingroup\$ The values outputted are off by one, I think Try it online! corrects that (but I've never used MATL before so...) \$\endgroup\$ – caird coinheringaahing Dec 4 '17 at 16:06
  • \$\begingroup\$ Check the end of my post. It provides the expected output, to which you are off by one on each. \$\endgroup\$ – Simply Beautiful Art Dec 4 '17 at 16:11
  • \$\begingroup\$ The first 5 values outputted by your current answer are 2 3 3 4 3, when the challenge says they should be 1 2 2 3 2 \$\endgroup\$ – caird coinheringaahing Dec 4 '17 at 16:11
  • \$\begingroup\$ @cairdcoinheringaahing and SimplyBeautifulArt Ah, I see. Thanks! Corrected now \$\endgroup\$ – Luis Mendo Dec 4 '17 at 16:13
6
\$\begingroup\$

Jelly, 12 11 10 9 bytes

³ḊÆṪÐĿ>1S

Try it online!

-1 byte thanks to HyperNeutrino!

-1 byte thanks to Mr. Xcoder!

-1 byte thanks to Dennis

How it works

³ḊÆṪÐĿ>1S - Main link. No arguments
³         - Yield 100
 Ḋ        - Dequeue. Creates the list [2, 3 ... 99, 100]
    ÐĿ    - For each element, while the results of the next function
          - aren't unique, collect the results...
  ÆṪ      -   Next function: Totient
      >1  - Greater than one?
        S - Sum the columns

As this was made by Dennis, I (understandably) have no idea why this works, just that it does.

\$\endgroup\$
  • 1
    \$\begingroup\$ @dylnan All three answers output the list of f(n) from 2 to 100, and the question doesn't mention input, so I think this is the correct version \$\endgroup\$ – caird coinheringaahing Dec 4 '17 at 16:09
  • \$\begingroup\$ @dylnan The challenge asks to output f for n=2 to n=100, not just one value. \$\endgroup\$ – Simply Beautiful Art Dec 4 '17 at 16:09
  • \$\begingroup\$ You're right, I had read the beginning of the challenge and didn't read the rules part clearly \$\endgroup\$ – dylnan Dec 4 '17 at 16:21
  • \$\begingroup\$ And with regards to the code, would it be possible to use # in this case? Something like this (which clearly doesn't work but written by someone who understands the syntax clearly!) \$\endgroup\$ – dylnan Dec 4 '17 at 16:23
  • \$\begingroup\$ @dylnan Possibly, but as we're generating a fixed list, to apply over each element, is usually better than #. \$\endgroup\$ – caird coinheringaahing Dec 4 '17 at 16:26
6
\$\begingroup\$

APL (Dyalog), 50 29 25 bytes

Look 'ma, no built-in totient!

4 bytes saved thanks to @H.PWiz

{⍵=1:0⋄1+∇+/1=⍵∨⍳⍵}¨1+⍳99

Try it online!

How?

Apparently I went for the longer (and harder) totient formula first. See revisions history.

⍳⍵ - 1 to n

⍵∨ - gcd with n

1= - equal to 1?

+/ - sum 'em all

This is the totient. All the rest is wrapper for the counting (1+∇) and applying on the range 2..100 (¨1+⍳99).

\$\endgroup\$
5
\$\begingroup\$

Mathematica, 44 bytes

(i=-1;#+1//.x_:>EulerPhi[++i;x];i)&~Array~99

-10 bytes from @Misha Lavrov
-2 bytes from @user202729

Try it online!

\$\endgroup\$
4
\$\begingroup\$

J REPL, 23 bytes

<:#@(5&p:^:a:)"0|2+i.99

I haven’t checked, but this probably works in regular J if you define it as a noun (I golfed this on my phone on the REPL).

Built-ins, yo.

I’d say that there are at least 2-3 bytes to shave off (off-by-one because of the way a: works, having to use | as a noop, etc.).

\$\endgroup\$
  • 1
    \$\begingroup\$ +/*<:5&p:^:a:2+i.99 for 19 bytes Try it online! \$\endgroup\$ – Galen Ivanov Dec 4 '17 at 19:12
  • \$\begingroup\$ For future reference, you can aso use "+ instead of "0, so it could equally become <:#@(5&p:^:a:)"+i.99 \$\endgroup\$ – Conor O'Brien Dec 4 '17 at 19:25
  • 2
    \$\begingroup\$ 16 bytes with +/1<a:5&p:2+i.99 \$\endgroup\$ – miles Dec 5 '17 at 2:44
  • 1
    \$\begingroup\$ @ miles : Can you explain the use of a: in your code? How does it work instead of ^:? \$\endgroup\$ – Galen Ivanov Dec 5 '17 at 7:34
  • 1
    \$\begingroup\$ @GalenIvanov (5&p:)^:a: m can be done as a: 5&p: m using the other definition of & when a dyad is bonded with a noun and then called dyadically. \$\endgroup\$ – miles Dec 5 '17 at 12:14
4
\$\begingroup\$

JavaScript (ES6), 115 ... 104 99 bytes

Hard-coding might be shorter, but let's try a purely mathematical approach.

f=n=>n>97?6:(P=(n,s=0)=>k--?P(n,s+(C=(a,b)=>b?C(b,a%b):a<2)(n,k)):s>1?1+P(k=s):1)(k=n+2)+' '+f(-~n)

console.log(f())

\$\endgroup\$
  • \$\begingroup\$ Hard-coding is 90 bytes (pastebin link) \$\endgroup\$ – Herman L Dec 4 '17 at 17:09
  • \$\begingroup\$ @HermanLauenstein Nicely done. \$\endgroup\$ – Arnauld Dec 4 '17 at 17:24
4
\$\begingroup\$

Python 2, 80 bytes

n,_=r=2,0;exec'r+=r[sum(k/n*k%n>n-2for k in range(n*n))]+1,;print r[n];n+=1;'*99

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Python 2, 82 bytes

l=0,1
exec"n=len(l);p=2\nwhile n%p:p+=1\nl+=l[p-1]+l[n/p]-n%4%3/2,;print l[n];"*99

Try it online!

This uses the observations that:

  • f(a*b) = f(a) + f(b) - 1, except the -1 is omitted if a and b are both even
  • f(p) = f(p-1) + 1 when p is prime, with f(2)=1

These imply that if n has prime factorization n = 2**a * 3**b * 5**c * 7**d * 11**e * ..., then f(n) = max(a,1) + b + 2*c + 2*d + 3*e + ..., where each p>2 in the factorization contributes f(p-1).

I'm not sure if these continue to hold past n=100, but if they do, they give a way to define and calculate f without using φ.

\$\endgroup\$
2
\$\begingroup\$

Bubblegum, 49 bytes

00000000: 5d88 0511 0020 0003 ab2c 024e ff64 e8a3  ].... ...,.N.d..
00000010: 379f 956b f05d 206c 0545 7274 743a b876  7..k.] l.Ertt:.v
00000020: 2267 27f9 9f4d 9b9d fc85 e7e6 994d 6eb0  "g'..M.......Mn.
00000030: 2b                                       +

Try it online!

\$\endgroup\$
2
\$\begingroup\$

PowerShell, 110 bytes

$a=,0*101;2..100|%{$i=$_;for($z=$j=0;++$j-lt$i;$z+=$k-eq1){for($k=$j;$j%$k-or$i%$k;$k--){}};($a[$i]=$a[$z]+1)}

Try it online!

Mathematical approach.

Actually, looking through it, very similar to the C answer, but developed independently. Creates an array of 0s, loops from 2 to 100, then calculates phi using the gcd formulation. The part in parens at the end both saves the result into $a for the next go-round, and places a copy on the pipeline, which results in the implicit output.


PowerShell, 112 bytes

"122323333434344534444545444545555545455645555655565646555656556656665656565656656757566756666667566"-split'(.)'

Try it online!

Hard-coded. Ho-hum. Shorter than I could get a mathematical approach by about 10-15 bytes.

\$\endgroup\$
  • \$\begingroup\$ I wonder whether you actually need a separator, as all the numbers are single digits:) \$\endgroup\$ – flawr Dec 4 '17 at 17:02
  • 1
    \$\begingroup\$ Can you show us your mathematical approach? It looks much more interesting certainly :P \$\endgroup\$ – Conor O'Brien Dec 5 '17 at 15:18
  • 2
    \$\begingroup\$ @ConorO'Brien Luckily enough, I was able to look at it with fresh eyes this morning and golf the mathematical approach below the hard-coded approach. \$\endgroup\$ – AdmBorkBork Dec 5 '17 at 16:11
2
\$\begingroup\$

Python 2, 83 bytes

n=2
exec"print len(bin(n))-3+n%2-~n%9/8-(0x951a5fddc040419d4005<<19>>n&1);n+=1;"*99

Try it online!

Combines a heuristic estimate with a hardcoded constant that corrects each estimate as either -0 or -1.

\$\endgroup\$
2
\$\begingroup\$

Husk, 10 17 bytes

mö←LU¡Sȯṁε⌋ḣtḣ100

Try it online!

Edit: +7 bytes for actually mapping the function over the range that was asked for, before it was only the function computing A003434.

Explanation

The following computes A003434:

←LU¡S(ṁ(ε⌋))ḣ -- takes a number as input, for example: 39
   ¡          -- iterate the following function on the input: [39,24,8,4,2,1,1,1..]
    S(     )ḣ --   with itself (x) and the range [1..x]..
      ṁ(  )   --   ..map and sum the following
        ε⌋    --     0 if gcd not 1 else 1
  U           -- longest unique prefix: [39,24,8,4,2,1]
 L            -- length: 6
←             -- decrement: 5

The m(....)ḣ100 part just map that function over the range [2..100], not sure how I missed that part before :S

\$\endgroup\$
1
\$\begingroup\$

PHP, 98 bytes

1,2,<?=join(',',str_split(unpack('H*','##3444E4DEEDEEUUEEVEUVUVVFUVVUfVfVVVVVegWVgVffgV')[1]))?>,6

Try it online!

I packed all digits into a binary string. After unpacking it, converting it to a an array and then mergin the array again, i only had to prepend the 1,2 and append the 6 as those wouldnt fit or caused a control code to appear.

\$\endgroup\$
1
\$\begingroup\$

Perl 6, 47 bytes

map {($_,{+grep 1==* gcd $_,^$_}...1)-1},2..200

Try it online!

\$\endgroup\$
1
\$\begingroup\$

05AB1E, 11 bytes

тL¦ε[DNs#sÕ

Try it online!

Explanation

тL¦           # push range [2 ... 100]
   ε          # apply to each
    [         # start a loop
     D        # duplicate the current number
      N       # push the loop iteration counter
       s      # swap one copy of the current number to the top of the stack
        #     # if true, break the loop
         s    # swap the second copy of the current number to the top of the stack
          Õ   # calculate eulers totient
\$\endgroup\$
1
\$\begingroup\$

C, 112 bytes

a[101];f(i,j,k,t){for(a[i=1]=0;i++<100;printf("%d ",a[i]=a[t]+1))for(t=j=0;++j<i;t+=k==1)for(k=j;j%k||i%k;k--);}

Ungolfed:

a[101];
f(i,j,k,t){
    for(a[1]=0,i=2;i<=100;i++) {   // initialize
        for(t=j=0;++j<i;t+=k==1)   // count gcd(i, j) == 1 (t = phi(i))
            for(k=j;j%k||i%k;k--); // calculate k = gcd(i, j)
        printf("%d ",a[i]=a[t]+1); // print and store results
    }
}

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Alumin, 87 bytes

hhhhhdadtqdhcpkkmzyhqkhwzydqhhwdrdhhhwrysrshhwqdrybpkshehhhwrysrarhcpkksyhaydhehycpkkmr

Try it online!

Explanation

hhhhhdadt      CONSTANT 100

RANGE FROM 100 to 0
q
  dhc
p

REMOVE 0 AND 1
kk

OVER EACH ELEMENT...
m
  zyh
  q
    kh
    wzyd
    q
      DUPLICATE TOP TWO ELEMENTS...
      hhwdrdhhhwrysrshhw
      GCD...
      qdryb
    p
    ks
    he
    hhhw
    ry
    s
    rarhc
  p
  IS IT ONE? IF SO TERMINATE (FIXPOINT)
  kksyhaydhehyc
p
kk
m
REVERSE THE VALUES
r
\$\endgroup\$
0
\$\begingroup\$

Pyth, 38 bytes (not competitive)

.e-+1sl+1kb_jC"Éõ4ÕYHø\\uÊáÛ÷â¿"3

Try it on the Pyth Herokuapp, because it doesn't work on TIO for whatever reason.

I have no doubt the explicit Pyth solution is smaller, but I wanted to see how small I could get the code by compressing the sequence, and learn Pyth I guess. This uses the fact that an upper bound of the sequence is log2(n)+1.

Explanation

.e-+1sl+1kb_jC"Éõ4ÕYHø\\uÊáÛ÷â¿"3
             C"Éõ4ÕYHø\\uÊáÛ÷â¿"   interpret string as base 256 integer
            j                   3  convert to array of base 3 digits
           _                       invert sequence (original had leading 0s)
.e                                 map with enumeration (k=index, b=element)
       +1k                                   k+1
     sl                            floor(log(   ))
   +1                                             +1
  -       b                                         -b

I got the compressed string via Ci_.e+1-sl+1ksb"122323333434344534444545444545555545455645555655565646555656556656665656565656656757566756666667566"3, which is just the opposite of the code above with a few type conversions.

\$\endgroup\$
  • 1
    \$\begingroup\$ Why noncompeting? \$\endgroup\$ – Simply Beautiful Art Dec 5 '17 at 18:18
  • \$\begingroup\$ @SimplyBeautifulArt didn't really mean noncompeting in the formal sense; edited the title to make that more clear \$\endgroup\$ – stellatedHexahedron Dec 5 '17 at 18:34
0
\$\begingroup\$

Ohm v2, 41 bytes

“ ‽W3>€þΣÌιZ§Á HgüυH§u·β}Bā€ΣNπáÂUõÚ,3“8B

Try it online!

Literally completely hardcoded... I actually took the sequence above, stripped everything that wasn't a number, interpreted it as base 8, then turned it into Ohm's built-in base 255 number representation. That's what the quotes do. Then, the program simply turns that into base 8 again.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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