兰道函数

对于所有非负整数,兰道函数$g(n)$定义为对称群$S_{n}$的所有元素的秩之中,最大的一个。或者说,$g(n)$是$n$的所有整数分拆之中的最小公倍数。

例如${\displaystyle 5=2+3}, {\displaystyle lcm(2,3)=6}$没有其他5的分割方式能得出一个更大的最小公倍数,故此${\displaystyle g(5)=6}$

{\displaystyle \lim _{n\to \infty }{\frac {\ln(g(n))}{\sqrt {n\ln(n)}}}=1}



(摘自WikiPedia – 蘭道函數)

OEIS – A000793 – landau function

MathWorld – Landau

g(0) = 1, g(1) = 1, g(2) = 2, g(3) = 3, g(4) = 4, g(5) = 6, g(6) = 6, g(7) = 12, g(8) = 15, …

上面的我也不懂

代码实现

从兰道函数的定义得知,我们要求的是将 n 分成 \lbrace x_1, x_2, x_3…x_k \rbrace后, max\big\lparen lcm \lparen x_1, x_2, x_3…x_k\rparen \big\rparen

暴力拆分
// C++ program for the above approach
#include 
using namespace std;
// To store Landau's function of the number
int Landau = INT_MIN;
// Function to return gcd of 2 numbers
int gcd(int a, int b)
{
    if (a == 0)
        return b;
    return gcd(b % a, a);
}
// Function to return LCM of two numbers
int lcm(int a, int b)
{
    return (a * b) / gcd(a, b);
}
// Function to find max lcm value
// among all representations of n
void findLCM(vector& arr)
{
    int nth_lcm = arr[0];
    for (int i = 1; i < arr.size(); i++)
        nth_lcm = lcm(nth_lcm, arr[i]);
    // Calculate Landau's value
    Landau = max(Landau, nth_lcm);
}
// Recursive function to find different
// ways in which n can be written as
// sum of atleast one positive integers
void findWays(vector& arr, int i, int n)
{
    // Check if sum becomes n,
    // consider this representation
    if (n == 0)
        findLCM(arr);
    // Start from previous element
    // in the representation till n
    for (int j = i; j <= n; j++) {
        // Include current element
        // from representation
        arr.push_back(j);
        // Call function again
        // with reduced sum
        findWays(arr, j, n - j);
        // Backtrack - remove current
        // element from representation
        arr.pop_back();
    }
}
// Function to find the Landau's function
void Landau_function(int n)
{
    vector arr;
    // Using recurrence find different
    // ways in which n can be written
    // as a sum of atleast one +ve integers
    findWays(arr, 1, n);
    // Print the result
    cout << Landau;
}
// Driver Code
int main()
{
    // Given N
    int N = 4;
    // Function Call
    Landau_function(N);
    return 0;
}

时间复杂度:\mathcal{O}(2^N)

空间复杂度:\mathcal{O}(N^2)

暴力拆分不是很好的策略,现证明 x_i = p ^ A,其中 p 为质数。

(update 2023.11.11)
假设我们拆分出来一个 x_i 是合数,那么该数对 lcm 的贡献最多是 x_i 。设 x_i = m \times q, (m, q) = 1, m > 1, n > 1。最后的贡献为 n \times m,那如果 n,m 互质,但有一个不是质数,这个数可以继续拆分。
现在考虑如何拆分,可以将每个这样的 x_i 拆成 \big\lbrace m, q, (mq -m – q) \big\rbrace,可以证明,mq – m – q \gt 0lcm 不会变小,和没有变化。那么就可以将 x_i 一直拆下去,直到全部拆成质数。

考虑 dp

dp[i][j] 表示数字 i 由前 j 个质数组成的最大取值。那么再枚举一个 k ,表示 p_j 的次数。

TLE Code
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 2005;
bool prime[N];
int p[N];
vector<vector<long long>> dp(N, vector<long long>(N));
vector<long long> ans(N);
int k;
void isprime() {
    k = 1;
    fill(prime, prime + N, true);
    for (int i = 2; i < N; i++) {
        if (prime[i]) {
            p[k++] = i;
            for (int j = i + i; j < N; j += i) {
                prime[j] = false;
            }
        }
    }
}
long long max(long long a, long long b) {
    return (a > b) ? a : b;
}
void Work() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < k; j++) {
            dp[i][j] = 1;
        }
    }
    for (int i = 1; i < k; i++) {
        dp[2][i] = 2;
    }
    for (int i = 3; i < N; i++) {
        for (int j = 1; j < k; j++) {
            dp[i][j] = dp[i][j - 1];
            int tmp = p[j];
            while (i >= tmp) {
                dp[i][j] = max(dp[i][j], dp[i - tmp][j - 1] * tmp);
                tmp *= p[j];
            }
        }
    }
    ans[0] = ans[1] = 1;
    ans[2] = 2;
    for (int i = 3; i < N; i++) {
        ans[i] = 0;
        for (int j = 1; j < k; j++) {
            ans[i] = max(ans[i], dp[i][j]);
        }
    }
}
int main() {
    isprime();
    Work();
    int n;
    while (cin >> n) {
        cout << ans[n] << endl;
    }
    return 0;
}

我们发现这个东西是个完全背包,一次有至多 n 种品种,逐次减小。那么 dp 可以优化到一维。

AC Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxd(x, y) ((x) > (y) ? (x) : (y))
#define mind(x, y) ((x) < (y) ? (x) : (y))
#define abs_sub(x, y) ((x) > (y) ? (x) - (y) : (y) - (x))
const double eps = 1e-8;
const int N = 4e4 + 10;
const double pi = acos(-1.0);
int n;
int cnt, p[5000], a[5000], flag[N];
double dp[N];
double l[N];
void get_prime() {
  l[1]=0;
  for(int i = 2; i < N; i++) {
    l[i] = log(1.0 * i);
    if(!flag[i]) p[++cnt] = i;
    for(int j = 1; j <= cnt; j++) {
      if(i * p[j] > N) break;
      flag[i * p[j]] = 1;
      if(i % p[j] == 0) break;
    }
  }
}

inline void solve() {
  for(int i = 1; i <= cnt; i++) {
    int tot = 0;
    for(int j = p[i]; j <= n; j *= p[i]) a[++tot] = j;//tot表示p能有多少种可能(完全背包!)
    for(int j = n; j >= a[1]; j--) {
      for(int k = 1; k <= tot; k++) {
        if(j >= a[k]) dp[j] = max(dp[j], dp[j - a[k]] + l[a[k]]);//看到这个方程是不是豁然开朗
      }
    }
  }
}
int main()
{
  // freopen("icecream.in", "r", stdin);
  // freopen("icecream.out", "w", stdout);
  scanf("%d", &n);
  get_prime();
  // cout << cnt;
  // Work();
  solve();
  printf("%.7f", dp[n]);
  return 0;
}