17
\$\begingroup\$

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
\$\endgroup\$
3
  • \$\begingroup\$ Probably useless here, but \$\operatorname{lcm}(1,2,\ldots,n)\$ is A003418. \$\endgroup\$ – Arnauld Jan 13 at 13:05
  • \$\begingroup\$ We don't need to calculate all integer partitions, right? Would all subsets of [1..n] where the sum doesn't exceed n work? \$\endgroup\$ – user Jan 13 at 16:11
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Bubbler Jan 13 at 23:27

13 Answers 13

7
\$\begingroup\$

Jelly, 15 14 bytes

:;Ɱæl/€ṀɗƬŒṗL’

Try it online!

Explanation

:;Ɱæ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
\$\endgroup\$
7
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ 69 bytes by putting all of (?) in a single definition. \$\endgroup\$ – ovs Jan 14 at 21:19
  • \$\begingroup\$ @ovs Nice find, I suggest you post an answer for the outgolfing bounty \$\endgroup\$ – xnor Jan 14 at 23:52
  • 1
    \$\begingroup\$ Done \$\endgroup\$ – ovs Jan 15 at 7:30
6
\$\begingroup\$

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
\$\endgroup\$
3
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – ovs Jan 13 at 10:49
  • \$\begingroup\$ @ovs Oh, nice approach with . This is indeed a lot better. Thanks for -6. \$\endgroup\$ – Kevin Cruijssen Jan 13 at 11:36
  • \$\begingroup\$ @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. \$\endgroup\$ – Kevin Cruijssen Jan 13 at 11:42
5
+100
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Don't know if small is an appropriate adjective wrt to golfing improvements over one of xnor's answers... +1 well done! :D \$\endgroup\$ – Noodle9 Jan 16 at 14:44
4
\$\begingroup\$

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``
\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
6
  • \$\begingroup\$ Looks like you can get the same length without imports from Lambdabot: Try it online! \$\endgroup\$ – xnor Jan 14 at 3:29
  • \$\begingroup\$ Some optimizations for 121: Try it online! \$\endgroup\$ – xnor Jan 14 at 3:34
  • \$\begingroup\$ 119 bytes by building off of @xnor's suggestions. \$\endgroup\$ – user Jan 14 at 16:16
  • \$\begingroup\$ Make that 116 (I imported Data.List since you're using Lambdabot) \$\endgroup\$ – user Jan 14 at 16:27
  • \$\begingroup\$ 107 with elemIndex. \$\endgroup\$ – user Jan 14 at 17:22
2
\$\begingroup\$

Charcoal, 100 bytes

≔⟦⟦N¹⟧⟧θFθ«≔⊟ιη≔⌊ιζ≔⊟ιε¿εF…·¹ζ⊞θ⁺ι⟦κ⁻εκ÷×ηκ⌈Φ⊕κ∧λ¬∨﹪κλ﹪ηλ⟧⊞υη»≔⟦¹⟧θW⁻Eυ÷×⌈θκ⌈Φ⊕κ∧μ¬∨﹪κμ﹪⌈θμθ⊞θ⌈ιI⊖Lθ

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

≔⟦⟦N¹⟧⟧θFθ«

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

¿εF…·¹ζ

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

W⁻Eυ÷×⌈θκ⌈Φ⊕κ∧μ¬∨﹪κμ﹪⌈θμθ

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.

I⊖Lθ

Print the index of the last term.

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

K (ngn/k), 84 77 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
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Do you need to define p when it is used only once? \$\endgroup\$ – Bubbler Jan 13 at 23:28
  • \$\begingroup\$ @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 \$\endgroup\$ – ngn Jan 14 at 21:23
2
\$\begingroup\$

Wolfram Language (Mathematica), 58 bytes

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

Try it online!

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

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)
\$\endgroup\$
2
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Neil Jan 13 at 23:07
  • \$\begingroup\$ @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 \$\endgroup\$ – user Jan 13 at 23:31
1
\$\begingroup\$

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!

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

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

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

Stax, 24 bytes

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

Run and debug it

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

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