# Landau logarithm

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

• Probably useless here, but $\operatorname{lcm}(1,2,\ldots,n)$ is A003418. – Arnauld Jan 13 at 13:05
• We don't need to calculate all integer partitions, right? Would all subsets of [1..n] where the sum doesn't exceed n work? – user Jan 13 at 16:11
• @user I think that works too, because 1) such a set has the same LCM as that set plus enough amount of ones to make the sum n, and 2) repeated partitions don't contribute to the LCM either. – Bubbler Jan 13 at 23:27

(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. • 69 bytes by putting all of (?) in a single definition. – ovs Jan 14 at 21:19 • @ovs Nice find, I suggest you post an answer for the outgolfing bounty – xnor Jan 14 at 23:52 • Done – ovs Jan 15 at 7:30 # Jelly, 1514 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  # 05AB1E, 2721 15 bytes 1.ΓIÅœsδª€.¿à}g  -6 bytes by porting @xigoi's Jelly answer, so make sure to upvote him! Original 27 21 bytes approach: 1[DIL.¿QD–#IÅœsδª€.¿à  -6 bytes thanks to @ovs. 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  • 21 bytes by using the iteration index and – to get the result, keeping the maximum lcm on top of the stack and only appending one lcm to each partition. – ovs Jan 13 at 10:49 • @ovs Oh, nice approach with –. This is indeed a lot better. Thanks for -6. – Kevin Cruijssen Jan 13 at 11:36 • @ovs Apparently a port of the Jelly answer is even shorter. The main part of the code remains the same though, so thanks again for those golfs. – Kevin Cruijssen Jan 13 at 11:42 # 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. • Don't know if small is an appropriate adjective wrt to golfing improvements over one of xnor's answers... +1 well done! :D – Noodle9 Jan 16 at 14:44 # 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  # 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  • Looks like you can get the same length without imports from Lambdabot: Try it online! – xnor Jan 14 at 3:29 • Some optimizations for 121: Try it online! – xnor Jan 14 at 3:34 • 119 bytes by building off of @xnor's suggestions. – user Jan 14 at 16:16 • Make that 116 (I imported Data.List since you're using Lambdabot) – user Jan 14 at 16:27 • 107 with elemIndex. – user Jan 14 at 17:22 # 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. # Wolfram Language (Mathematica), 58 bytes ((i=1)//.n_:>Max[i--;n~LCM~##&@@@IntegerPartitions@#];-i)&  Try it online! # 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

• Do you need to define p when it is used only once? – Bubbler Jan 13 at 23:28
• @Bubbler thanks. i can also make f dyadic and pass l as its first arg (x) to make a partial application, and rename the old x to y. that saves another 3 bytes – ngn Jan 14 at 21:23

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

• That subsets trick looks valid to me! For any given integer partition, a subset with the same LCM can be obtained by deduplicating its terms. Furthermore, for any subset, an integer partition with the same LCM can be obtained by adding sufficient 1s. The two sets of LCMs are therefore equal. – Neil Jan 13 at 23:07
• @Neil That's what I was thinking. Bubbler thinks so too, so I'm going to go ahead and move the 185-byte answer to the top – user Jan 13 at 23:31

# Python 3, 128 123 bytes

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!

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

# Stax, 24 bytes

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


Run and debug it

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