Landau logarithm

Question

Related: Landau's function (OEIS A000793)

Background

Landau's function \$g(n)\$ is defined as the largest order of permutation of \$n\$ elements, which is equal to \$\max(\operatorname{lcm}(a_1,a_2,\cdots,a_i))\$ where \$a_1,a_2,\cdots,a_i\$ is an integer partition of \$n\$.

We can extend this to define "iterations" of Landau's function: let's define \$g_0(n) = 1\$, and \$g_{k+1}(n) = \max(\operatorname{lcm}(g_{k}(n), a_1,a_2,\cdots,a_i))\$ for \$k \ge 0\$. This eventually converges to \$\operatorname{lcm}(1,2,\cdots,n)\$, so we can define "Landau logarithm" to be the smallest value of \$k\$ such that \$g_k(n)=\operatorname{lcm}(1,2,\cdots,n)\$, or equivalently \$g_k(n)=g_{k+1}(n)\$.

The resulting sequence is OEIS A225633.

Illustration

n = 5

To make it clear, let's list up all the integer partitions of 5, which are:

(5)
(4, 1)
(3, 2)
(3, 1, 1)
(2, 2, 1)
(2, 1, 1, 1)
(1, 1, 1, 1, 1)

By definition, \$g_0(5) = 1\$. \$g_1(5)\$ is defined by whatever partition gives the largest LCM, which is \$\operatorname{lcm}(2,3) = 6\$ (which is the same as the plain Landau function). \$g_2(5)\$ is the largest LCM of any partition when combined with 6. We need to find the partition which can give the largest additional factor. Such partition is plain 5, so \$g_2(5) = \operatorname{lcm}(6,5) = 30\$. In the next step, the only partition that boosts the LCM further is (4,1), giving \$g_3(5) = \operatorname{lcm}(30, 4, 1) = 60\$, which is the same as \$\operatorname{lcm}(1, 2, 3, 4, 5)\$. Therefore, the Landau logarithm of 5 is 3.

n = 10

• \$g_0(10) = 1\$
• \$g_1(10) = \operatorname{lcm}(2,3,5) = 30\$
• \$g_2(10) = \operatorname{lcm}(30,7,3) = 210\$
• \$g_3(10) = \operatorname{lcm}(210,8,2) = 840\$
• \$g_4(10) = \operatorname{lcm}(840,9,1) = 2520 = \operatorname{lcm}(1,2,\cdots,10)\$

Therefore the Landau logarithm of 10 is 4.

Challenge

Given a positive integer \$n\$, compute its Landau logarithm.

The shortest code in bytes wins.

Test cases

The first 20 terms (starting at n=1, up to n=20 inclusive) are:

0, 1, 2, 2, 3, 3, 3, 3, 4, 4,
5, 5, 6, 5, 5, 5, 6, 6, 7, 6

Answer 1

Haskell, 72 bytes

(1%)
k%n|k?n==k=0|1>0=1+k?n%n
k?0=k
k?n=maximum[lcm x$k?(n-x)|x<-[1..n]]

Try it online!

The helper function k?n compute a the Landau function g(n) except k is also in the list of numbers. Then, k%n counts how many iterations of replacing x with x?n starting with k we need to reach a fixed point.

Answer 2

Haskell, 69 bytes

A small improvement to xnor's answer.

(1%)
k%n|k?n==k=0|1>0=1+k?n%n
k?n=maximum$k:[lcm x$k?(n-x)|x<-[1..n]]

Try it online!

Compared to the original solution I have simplified the definition of k?n, which calculates one iteration of the Landau function.
For \$n=0\$ the function returns \$k\$ and for positive \$n\$ it always returns the \$\mathop{lcm}\$ of \$k\$ and some positive integers, which is greater than or equal to \$k\$.
Since [1..n] is empty for \$n=0\$, we can get rid of an explicit base case by prepending \$k\$ to the list of possible results.

Answer 3

Jelly, 15 14 13 bytes

:ælƒ€@Ṁ¥ƬŒṗL’

Try it online!

Explanation (older version)

:;Ɱæl/€ṀɗƬŒṗL’   Main monadic link
:                Divide the input by itself to get 1
         Ƭ       Repeat until reaching fixed point, collecting intermediate results
        ɗ        (
 ;Ɱ       Œṗ       Prepend to each integer partition of the input
      €            For each
     /             fold over
   æl              the lowest common multiple
       Ṁ           Maximum
        ɗ        )
            L    Length
             ’   Decrement

Answer 4

05AB1E, 27 21 15 bytes

1.ΓIÅœs䪀.¿à}g

-6 bytes by porting @xigoi's Jelly answer, so make sure to upvote him!

Try it online or verify all test cases.

Original 27 21 bytes approach:

1[DIL.¿QD–#IÅœs䪀.¿à

-6 bytes thanks to @ovs.

Try it online or verify all test cases.

Explanation:

1             # Push 1
 .Γ           # Loop until it no longer changes, collecting intermediate results:
   I          #  Push the input-integer
    Ŝ        #  Pop and push all lists of positive integers that sum to this input
       δ      #  Map over each of these lists:
      s ª     #   And add the current value as trailing item to each
         €    #  Then map over each of these lists again:
          .¿  #   And calculate its least common multiple
            à #  Pop this list of lcm's, and only leave the maximum
 }g           # After the loop: pop and push its length
              # (after which it is output implicitly as result)

1             # Push 1
 [            # Start an infinite loop:
  D           #  Duplicate the current value on the stack
   IL         #  Push a list in the range [1,input]
     .¿       #  Pop and get the least common multiple of this list
   Q          #  If this is equal to the current value we've duplicated:
     –        #   Print the (0-based) loop-index
    D #       #   And stop the infinite loop/program
   IÅœs䪀.¿à #  Same as above

Answer 5

JavaScript (ES6),  145  116 bytes

n=>~(G=(a,b)=>b?G(b,a%b):a,P=(p,n,i=1)=>m=n?i>n||Math.max(P(p*i/G(p,i),n-i,i),P(p,n,i+1)):p,h=p=>P(p,n)-p&&h(m)-1)``

Try it online!

Commented

The helper function \$G\$ computes \$\gcd(a,b)\$.

G = (a, b) => b ? G(b, a % b) : a

The helper function \$P(p,n)\$ recursively computes all integer partitions of \$n\$ while keeping track of the maximum \$\operatorname{lcm}\$ of the union of the partition and \$p\$. This maximum is eventually saved in \$m\$ and returned.

P = (                               // P is a recursive function taking:
  p,                                //   p = previous maximum
  n,                                //   n = input of the main function
  i = 1                             //   i = counter for the current partition
) =>                                //
m =                                 // save the final result in m
  n ?                               // if n is not equal to 0:
    i > n ||                        //   return 1 if i is greater than n
    Math.max(                       //   otherwise return the maximum of:
      P(p * i / G(p, i), n - i, i), //     a recursive call with p = lcm(p, i)
                                    //     and n = n - i
      P(p, n, i + 1)                //     a recursive call with i + 1
    )                               //   end of Math.max()
  :                                 // else:
    p                               //   stop the recursion and return p

The helper function \$h\$ updates the maximum \$m\$ until a fixed point is reached and keeps track of the total number of iterations (as a negative value).

h = p => P(p, n) - p && h(m) - 1

The main wrapper function just processes the initial call to \$h\$ with \$p\$ zero'ish and bitwise-inverts the result.

n => ~h``

Answer 6

Haskell (Lambdabot), 127 bytes

l=foldl1 lcm
p 0=[[]]
p n=[1..n]>>= \x->(x:)<$>p(n-x)
n#v=maximum$fmap(l.(v:))$p n
s n=fromJust$elemIndex(l[1..n])$iterate(n#)1

s is the "main" function. Requires Data.List and Data.Maybe from lambdabot to run.

Ungolfed:

-- LCM of a list; it saves a few bytes to define a shortcut to it.
l = foldl1 lcm

-- Given an integer n, this function gives us all partitions of n.
-- The list monad is excellent for "enumeration" sorts of problems
-- like this.
p 0 = [[]]
p n = [1..n] >>= \x -> (x: ) <$> p (n - x)

-- Given an integer n and a previous Landau value v, this function
-- (whose name is the infix operator (#)) produces the "next" Landau
-- iteration value.
n # v = maximum $ fmap (l . (v :)) $ p n

-- Given an integer n, we iterate the (#) function until we find the
-- number `l [1..n]' (the lcm of 1 up to n) and then we return the index
-- of that number. Unfortunately, elemIndex returns `Maybe Int' so we need
-- the rather lengthy fromJust to get rid of that.
s n = fromJust $ elemIndex (l [1..n]) $ iterate (n #) 1

Answer 7

Wolfram Language (Mathematica), 58 bytes

((i=1)//.n_:>Max[i--;n~LCM~##&@@@IntegerPartitions@#];-i)&

Try it online!

Answer 8

Haskell, 68 67 bytes

k%n=sum[1+k?n%n|k?n>k]
k?n=maximum$k:[lcm x$k?(n-x)|x<-[1..n]]

(1%)

Try it online!

Golfs 2 bytes off of ovs' answer which itself golfed 3 bytes off xnor's answer.

Answer 9

Charcoal, 100 bytes

≔⟦⟦Ｎ¹⟧⟧θＦθ«≔⊟ιη≔⌊ιζ≔⊟ιε¿εＦ…·¹ζ⊞θ⁺ι⟦κ⁻εκ÷×ηκ⌈Φ⊕κ∧λ¬∨﹪κλ﹪ηλ⟧⊞υη»≔⟦¹⟧θＷ⁻Ｅυ÷×⌈θκ⌈Φ⊕κ∧μ¬∨﹪κμ﹪⌈θμθ⊞θ⌈ιＩ⊖Ｌθ

Try it online! Link is to verbose version of code. Explanation:

≔⟦⟦Ｎ¹⟧⟧θＦθ«

Start a breadth-first search for integer partitions of \$ n \$. Each partition is represented by a list of terms \$ a_1, a_2, ..., a_i, r, l \$ where the residue \$ r = n - \sum a_k \$ and the LCM \$ l = \operatorname{lcm}(a_1, a_2, ..., a_i) \$ , so as the initial partition has no terms yet, the residue is just \$ n \$ and the lcm is \$ 1 \$.

≔⊟ιη≔⌊ιζ≔⊟ιε

Extract \$ l, r, \$ and \$ \operatorname{min}(a_1, a_2, ..., a_i, r) \$ (which is the maximum possible next term of the partition).

¿εＦ…·¹ζ

If \$ r \$ is non-zero, then looping over each valid next term...

⊞θ⁺ι⟦κ⁻εκ÷×ηκ⌈Φ⊕κ∧λ¬∨﹪κλ﹪ηλ⟧

... concatenate the previous terms with the current term, the new residue, and the new LCM (calculated manually by dividing the product by the maximum of all common factors).

⊞υη

Otherwise this is a complete partition so save the LCM to the predefined empty list.

»≔⟦¹⟧θ

Now start building up the terms of \$ g \$ starting with \$ g_0(n) = 1 \$.

Ｗ⁻Ｅυ÷×⌈θκ⌈Φ⊕κ∧μ¬∨﹪κμ﹪⌈θμθ

Take the LCM of each of the partition LCMs with the maximum \$ g \$ value (i.e. the latest \$ g_i \$), but remove those whose LCM was still that value. Repeat while LCMs still remain.

⊞θ⌈ι

Add the highest LCM to the \$ g \$ list.

Ｉ⊖Ｌθ

Print the index of the last term.

Answer 10

K (ngn/k), 84 78 bytes

-4 thanks to @Bubbler

{#1_(|/(x/'{$[x;,/i,''(x-i)o'y&i:1+!x&y;,!0]}/2#y)x')\1}{_x*y%*|(*:)(|!\)/x,y}

Try it online!

/ungolfed
p:{$[x;,/i,''(x-i)o'y&i:1+!x&y;,!0]} /partitions
g:*|(*:)(|!\)/                       /gcd
l:{_x*y%g x,y}                       /lcm
f:{#1_(|/(l/'p/2#x)l')\1}            /landau log

Answer 11

Scala, 226 185 bytes

n=>Stream.iterate(1){z=>1.to(n).toSet.subsets.filter(_.sum<=n).map(?(_,z)).max}indexWhere?(1.to(n).toSet,1).==
val? =(_:Set[Int])./:(_:Int)((a,b)=>Stream.from(a).find(x=>x%a+x%b<1).get)

Try it online!

This is embarrassingly long and inefficient. Instead of finding integer partitions of n, this finds all subsets of the range [1..n] where the sum does not exceed n.

? is a helper function that finds the lcm of its second argument (a number) and all the elements in its first argument (a list). It does this by folding over the first argument with the second as the initial accumulator.

n =>
Stream.iterate(1){z=>  //Make infinite list by repeatedly apply this function to 1
  1.to(n).toSet.subsets //All subsets of range 1..n
    .filter(_.sum <= n) //Keep the ones whose sum is not greater than n
    .map(?(_,z))        //lcm of each (including g_{k-1}(n))
    .max                //Max
} indexWhere            //Find the index k where
  ?(1.to(n).toSet,1)    //The lcm of 1..n
    .==                 //equals g_k(n)

Answer 12

Python 3, 128 123 bytes

Apparently this uses a very similar approach as xnor's Haskell answer.

from math import*
f=lambda n,d=1:d-g(n,d)and-~f(n,g(n,d))
g=lambda n,d:max([g(n-k,k*d//gcd(k,d))for k in range(1,n+1)]+[d])

Try it online!

Answer 13

Python 3, 266 bytes

from math import*
p=lambda n:{(n,)}|{tuple(sorted((i,)+m))for i in range(1,n)for m in p(n-i)}
c=lambda l,r=1:l and c(l,r*l[-1]//gcd(r,l.pop()))or r
g=lambda i,n:i and max(c([g(i-1,n)]+[*e])for e in p(n))or 1
l=lambda n,p=0,i=0:p-g(i,n)and l(n,g(i,n),i+1) or i and~-i

Try it online!

Quite verbose! With main function \$l\$ and its helper functions \$g\$ (which is the same \$g\$ as in the OP), \$c\$ (aka \$lcm\$), and \$p\$ (which returns the partitions of \$n\$).

Answer 14

Stax, 24 bytes

╘J∙╢☼♥DÉ♀→⌂NP¶▐↓╚∞J¼╣øCû

Run and debug it

Algorithm borrowed from Kevin Cruijssen's answer, can probably be optimized further.