Iterated phi sequence

13

1

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

Simply Beautiful Art

Posted 2017-12-04T15:52:50.033

Reputation: 2 140

@LuisMendo Fixed, and also added graph + values to check against. :-) – Simply Beautiful Art – 2017-12-04T16:04:08.247

1

I've edited in the kolmogorov-complexity tag, as this is essentially outputting a fixed value

– caird coinheringaahing – 2017-12-04T16:10:23.293

[tags:kolmogorov-complexity] is correct in this case, though it is (probably) much shorter to implement the function. If you ask the question backwards (given the values, write a program printing the values) there will probably be no-one figure that out. – user202729 – 2017-12-04T16:19:38.623

@user202729 Oh god, that sounds very complicated. Hm... – Simply Beautiful Art – 2017-12-04T16:20:56.937

Which "that" are you referring to? – user202729 – 2017-12-04T16:22:47.323

@user202729 The reverse engineering/question backwards. – Simply Beautiful Art – 2017-12-04T16:23:40.287

@user202729 You think nobody would look up the values in the OEIS first thing? – Misha Lavrov – 2017-12-04T16:29:25.327

Hm, if f^-1(n) returns the set of values such that f(x) = n, I wonder if this set is finite for all n. – Simply Beautiful Art – 2017-12-04T16:30:36.543

@MishaLavrov Ok, without OEIS lookup, it is hard. A3434.

– user202729 – 2017-12-04T16:31:05.670

1@SimplyBeautifulArt First prove that there are finitely many values x such that phi(x) is a particular fixed number. – user202729 – 2017-12-04T16:31:46.803

2This 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?) – Uriel – 2017-12-04T16:35:52.977

@SimplyBeautifulArt According to Wikipedia, we have a lower bound on φ(n) on the order of n/log log n, so there's only a finite range in which a particular value of f can be achieved.

– Misha Lavrov – 2017-12-04T16:37:26.353

1: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 – Simply Beautiful Art – 2017-12-04T16:37:30.073

Ah, nice find @MishaLavrov – Simply Beautiful Art – 2017-12-04T16:37:54.253

@SimplyBeautifulArt not really, my language of choice can handle the wrapper pretty easily. But it feels like an overhead (somewhat redisual). Anyway, good challenge – Uriel – 2017-12-04T16:43:36.430

Do we need to separate the numbers or is an output of 122323333434344534444545444545555545455645555655565646555656556656665656565656656757566756666667566 allowed? – ovs – 2017-12-04T18:21:40.750

@ovs they need to be separated somehow. – Simply Beautiful Art – 2017-12-04T18:44:09.297

Answers

10

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]

H.PWiz

Posted 2017-12-04T15:52:50.033

Reputation: 10 962

7

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)

Luis Mendo

Posted 2017-12-04T15:52:50.033

Reputation: 87 464

1

The values outputted are off by one, I think Try it online! corrects that (but I've never used MATL before so...)

– caird coinheringaahing – 2017-12-04T16:06:25.620

Check the end of my post. It provides the expected output, to which you are off by one on each. – Simply Beautiful Art – 2017-12-04T16:11:20.770

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 – caird coinheringaahing – 2017-12-04T16:11:23.443

@cairdcoinheringaahing and SimplyBeautifulArt Ah, I see. Thanks! Corrected now – Luis Mendo – 2017-12-04T16:13:31.460

7

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!

flawr

Posted 2017-12-04T15:52:50.033

Reputation: 40 560

1This is pretty short for not having a totient builtin! – Luis Mendo – 2017-12-04T16:40:36.693

1

@LuisMendo H.PWiz found a solution that is even shorter!

– flawr – 2017-12-04T17:13:13.683

6

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.

caird coinheringaahing

Posted 2017-12-04T15:52:50.033

Reputation: 13 702

1@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 – caird coinheringaahing – 2017-12-04T16:09:30.993

@dylnan The challenge asks to output f for n=2 to n=100, not just one value. – Simply Beautiful Art – 2017-12-04T16:09:31.053

You're right, I had read the beginning of the challenge and didn't read the rules part clearly – dylnan – 2017-12-04T16:21:12.583

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!)

– dylnan – 2017-12-04T16:23:32.417

@dylnan Possibly, but as we're generating a fixed list, to apply over each element, € is usually better than #. – caird coinheringaahing – 2017-12-04T16:26:06.953

@HyperNeutrino Aww, but now I have to rewrite the explanation :P Thanks – caird coinheringaahing – 2017-12-04T17:17:08.333

@Mr.Xcoder Do you mind if I "take" that as a golf? – caird coinheringaahing – 2017-12-04T17:46:28.730

@cairdcoinheringaahing That was a golfing suggestion, so go ahead and edit that in – Mr. Xcoder – 2017-12-04T17:50:36.060

@Dennis or anyone else: is it possible in a # loop to return a list of the truthy values found instead of the list of indices which evaluate to a truthy value? – dylnan – 2017-12-04T18:08:52.703

@dylnan There is a chat room specifically about asking questions about Jelly, and another about learning Jelly, just to let you know, as you seem interested in the language.

– caird coinheringaahing – 2017-12-04T18:10:46.177

It's not that different from your original code. ÐĿ loops until ÆṪ returns a list of 99 ones, >1 maps all non-1 values to 1, then S sums, effectively counting the number of non-1's in each column. – Dennis – 2017-12-04T18:17:12.987

@Dennis Yeah, I'm starting to understand it now. Thanks! – caird coinheringaahing – 2017-12-04T18:20:47.357

6

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).

Uriel

Posted 2017-12-04T15:52:50.033

Reputation: 11 708

5

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!

J42161217

Posted 2017-12-04T15:52:50.033

Reputation: 15 931

4

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())

Arnauld

Posted 2017-12-04T15:52:50.033

Reputation: 111 334

Hard-coding is 90 bytes (pastebin link)

– Herman L – 2017-12-04T17:09:52.037

@HermanLauenstein Nicely done. – Arnauld – 2017-12-04T17:24:24.733

4

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.).

cole

Posted 2017-12-04T15:52:50.033

Reputation: 3 526

1+/*<:5&p:^:a:2+i.99 for 19 bytes Try it online! – Galen Ivanov – 2017-12-04T19:12:48.443

For future reference, you can aso use "+ instead of "0, so it could equally become <:#@(5&p:^:a:)"+i.99 – Conor O'Brien – 2017-12-04T19:25:35.953

216 bytes with +/1<a:5&p:2+i.99 – miles – 2017-12-05T02:44:45.377

1@ miles : Can you explain the use of a: in your code? How does it work instead of ^:? – Galen Ivanov – 2017-12-05T07:34:38.853

1@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. – miles – 2017-12-05T12:14:35.107

@miles Thank you! Now I see it's explained in the vocabulary too. – Galen Ivanov – 2017-12-05T12:28:45.323

4

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!

Dennis

Posted 2017-12-04T15:52:50.033

Reputation: 196 637

3

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 φ.

xnor

Posted 2017-12-04T15:52:50.033

Reputation: 115 687

2

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.

AdmBorkBork

Posted 2017-12-04T15:52:50.033

Reputation: 41 581

I wonder whether you actually need a separator, as all the numbers are single digits:) – flawr – 2017-12-04T17:02:23.607

1Can you show us your mathematical approach? It looks much more interesting certainly :P – Conor O'Brien – 2017-12-05T15:18:45.160

2@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. – AdmBorkBork – 2017-12-05T16:11:19.913

2

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!

ovs

Posted 2017-12-04T15:52:50.033

Reputation: 21 408

2

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.

xnor

Posted 2017-12-04T15:52:50.033

Reputation: 115 687

2

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

ბიმო

Posted 2017-12-04T15:52:50.033

Reputation: 15 345

1

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.

RFSnake

Posted 2017-12-04T15:52:50.033

Reputation: 41

1

Perl 6, 47 bytes

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

Try it online!

Sean

Posted 2017-12-04T15:52:50.033

Reputation: 4 136

1

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

Emigna

Posted 2017-12-04T15:52:50.033

Reputation: 50 798

1

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!

Colera Su

Posted 2017-12-04T15:52:50.033

Reputation: 2 291

0

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

Conor O'Brien

Posted 2017-12-04T15:52:50.033

Reputation: 36 228

0

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.

stellatedHexahedron

Posted 2017-12-04T15:52:50.033

Reputation: 871

1Why noncompeting? – Simply Beautiful Art – 2017-12-05T18:18:12.927

@SimplyBeautifulArt didn't really mean noncompeting in the formal sense; edited the title to make that more clear – stellatedHexahedron – 2017-12-05T18:34:15.420

0

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.

ThePlasmaRailgun

Posted 2017-12-04T15:52:50.033

Reputation: 383

Asked: 2017-12-04T15:52:50.033

Viewed: 1 607 times

Active: 2017-12-11T20:08:28.737