Iterated phi sequence

Question

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:

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

@LuisMendo Fixed, and also added graph + values to check against. :-) — Simply Beautiful Art, Dec 4 '17 at 16:04
I've edited in the kolmogorov-complexity tag, as this is essentially outputting a fixed value — caird coinheringaahing, Dec 4 '17 at 16:10
@SimplyBeautifulArt First prove that there are finitely many values x such that phi(x) is a particular fixed number. — user202729, Dec 4 '17 at 16:31
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?) — Uriel, Dec 4 '17 at 16:35
: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, Dec 4 '17 at 16:37

H.PWiz · Accepted Answer · 2017-12-04 17:22:54Z

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]

edited Dec 4 '17 at 17:22

answered Dec 4 '17 at 17:12

H.PWiz

11.1k2 gold badges15 silver badges55 bronze badges

add a comment |

flawr · Accepted Answer · 2017-12-04 17:06:34Z

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!

edited Dec 4 '17 at 17:06

answered Dec 4 '17 at 16:33

flawr

41.3k7 gold badges92 silver badges235 bronze badges

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

add a comment |

Mr. Xcoder · Accepted Answer · 2017-12-04 18:31:24Z

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)

The values outputted are off by one, I think Try it online! corrects that (but I've never used MATL before so...) — caird coinheringaahing, Dec 4 '17 at 16:06
Check the end of my post. It provides the expected output, to which you are off by one on each. — Simply Beautiful Art, Dec 4 '17 at 16:11
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, Dec 4 '17 at 16:11
@cairdcoinheringaahing and SimplyBeautifulArt Ah, I see. Thanks! Corrected now — Luis Mendo, Dec 4 '17 at 16:13

caird coinheringaahing · Accepted Answer · 2017-12-04 18:05:02Z

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.

edited Dec 4 '17 at 18:05

answered Dec 4 '17 at 15:59

caird coinheringaahing

22.5k5 gold badges53 silver badges159 bronze badges

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

| show 7 more comments

Uriel · Accepted Answer · 2017-12-04 18:44:47Z

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

Community · Accepted Answer · 2020-06-17 09:04:33Z

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!

edited Jun 17 '20 at 9:04

Community♦

1

answered Dec 4 '17 at 16:06

J42161217

20.3k2 gold badges22 silver badges70 bronze badges

add a comment |

cole · Accepted Answer · 2017-12-04 17:07:18Z

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

answered Dec 4 '17 at 17:07

cole

3,8661 gold badge9 silver badges24 bronze badges

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

| show 1 more comment

Community · Accepted Answer · 2020-06-17 09:04:33Z

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

edited Jun 17 '20 at 9:04

Community♦

1

answered Dec 4 '17 at 16:23

Arnauld

139k12 gold badges147 silver badges512 bronze badges

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

add a comment |

Dennis · Accepted Answer · 2017-12-05 02:28:43Z

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!

answered Dec 5 '17 at 2:28

Dennis

200k40 gold badges342 silver badges782 bronze badges

add a comment |

xnor · Accepted Answer · 2017-12-05 11:22:02Z

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

ovs · Accepted Answer · 2017-12-04 18:46:14Z

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!

answered Dec 4 '17 at 18:46

ovs

32.2k2 gold badges20 silver badges92 bronze badges

add a comment |

AdmBorkBork · Accepted Answer · 2017-12-05 16:10:38Z

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

edited Dec 5 '17 at 16:10

answered Dec 4 '17 at 16:57

AdmBorkBork

42.2k4 gold badges88 silver badges276 bronze badges

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

add a comment |

xnor · Accepted Answer · 2017-12-06 03:00:02Z

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.

answered Dec 6 '17 at 3:00

xnor

128k21 gold badges238 silver badges565 bronze badges

add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

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

RFSnake · Accepted Answer · 2017-12-04 18:16:16Z

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.

edited Dec 4 '17 at 18:16

answered Dec 4 '17 at 17:55

RFSnake

714 bronze badges

add a comment |

Sean · Accepted Answer · 2017-12-04 19:13:13Z

1

Perl 6, 47 bytes

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

Try it online!

answered Dec 4 '17 at 19:13

Sean

4,3966 silver badges10 bronze badges

add a comment |

Emigna · Accepted Answer · 2017-12-05 07:27:11Z

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

Community · Accepted Answer · 2020-06-17 09:04:33Z

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!

edited Jun 17 '20 at 9:04

Community♦

1

answered Dec 5 '17 at 10:16

Colera Su

2,3117 silver badges27 bronze badges

add a comment |

Conor O'Brien · Accepted Answer · 2017-12-05 15:15:16Z

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

Community · Accepted Answer · 2020-06-17 09:04:33Z

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.

@SimplyBeautifulArt didn't really mean noncompeting in the formal sense; edited the title to make that more clear — stellatedHexahedron, Dec 5 '17 at 18:34

ThePlasmaRailgun · Accepted Answer · 2017-12-11 20:08:28Z

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.

Stack Exchange Network

current community

your communities

more stack exchange communities

Iterated phi sequence

Rules:

21 Answers 21

Haskell, 53 52 bytes

Haskell, 70 69 68 bytes

MATL, 16 15 bytes

Explanation

Old version, 16 bytes

Explanation

Jelly, 12 11 10 9 bytes

How it works

APL (Dyalog), 50 29 25 bytes

Mathematica, 44 bytes

J REPL, 23 bytes

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

Python 2, 80 bytes

Python 2, 82 bytes

Bubblegum, 49 bytes

PowerShell, 110 bytes

PowerShell, 112 bytes

Python 2, 83 bytes

Husk, 10 17 bytes

Explanation

PHP, 98 bytes

Perl 6, 47 bytes

05AB1E, 11 bytes

C, 112 bytes

Alumin, 87 bytes

Explanation

Pyth, 38 bytes (not competitive)

Explanation

Ohm v2, 41 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged code-golf math sequence kolmogorov-complexity number-theory or ask your own question.

Linked

Hot Network Questions

Iterated phi sequence

Rules:

21 Answers 21

Haskell, 53 52 bytes

Haskell, 70 69 68 bytes

MATL, 16 15 bytes

Explanation

Old version, 16 bytes

Explanation

Jelly, 12 11 10 9 bytes

How it works

APL (Dyalog), 50 29 25 bytes

Mathematica, 44 bytes

J REPL, 23 bytes

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

Python 2, 80 bytes

Python 2, 82 bytes

Bubblegum, 49 bytes

PowerShell, 110 bytes

PowerShell, 112 bytes

Python 2, 83 bytes

Husk, 10 17 bytes

Explanation

PHP, 98 bytes

Perl 6, 47 bytes

05AB1E, 11 bytes

C, 112 bytes

Alumin, 87 bytes

Explanation

Pyth, 38 bytes (not competitive)

Explanation

Ohm v2, 41 bytes

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golf math sequence kolmogorov-complexity number-theory or ask your own question.

Linked

Related

Hot Network Questions