- 注册时间
- 2007-12-27
- 最后登录
- 1970-1-1
- 威望
- 星
- 金币
- 枚
- 贡献
- 分
- 经验
- 点
- 鲜花
- 朵
- 魅力
- 点
- 上传
- 次
- 下载
- 次
- 积分
- 51176
- 在线时间
- 小时
|
发表于 2026-4-30 19:06:28
|
显示全部楼层
k=6,n<=6的定制程序可以轻松搜索完m<=100000的范围(前面代码搜索到5000左右就卡住了),可以并没有找到新的解,主要方案AI汇总如下
# k=6, n≤6 定制搜索代码总结
## 核心思想
对于本原解,m 不是 2, 3, 7 的倍数。利用 42=2×3×7 的因子分解,将 m^6 的分解问题转化为:先确定 1-3 个"特殊数"(满足特定模条件),再搜索剩余的 42 倍数。
## 五种 Case 分类
根据 x2(非2倍数), x3(非3倍数), x7(非7倍数) 三者是否合并:
| Case | 确定数 | 约束 | 余下搜索 | 候选数 |
|------|--------|------|---------|--------|
| 1: x2=x3=x7 | 1个x | x^6≡m^6 (mod 42^6) | ≤5个42倍数 | 144 |
| 2: x2=x3≠x7 | x23, x7 | x23:7倍数, x7:6倍数 | ≤4个42倍数 | 24×6 |
| 3: x2=x7≠x3 | x27, x3 | x27:3倍数, x3:14倍数 | ≤4个42倍数 | 24×6 |
| 4: x3=x7≠x2 | x37, x2 | x37:2倍数, x2:21倍数 | ≤4个42倍数 | 36×4 |
| 5: 全不同 | x2,x3,x7 | x2:21倍, x3:14倍, x7:6倍 | ≤3个42倍数 | 4×6×6 |
## 候选模数
| 变量 | 模数 | 值 | 候选残基数 |
|------|------|-----|-----------|
| Case1 x | 64×729×117649 | 5,489,031,744 | 144 |
| Case2 x23 | 64×729×7 | 326,592 | 24 |
| Case2 x7 | 6×117649 | 705,894 | 6 |
| Case3 x27 | 64×117649×3 | 22,588,608 | 24 |
| Case3 x3 | 14×729 | 10,206 | 6 |
| Case4 x37 | 729×117649×2 | 171,532,242 | 36 |
| Case4 x2 | 21×64 | 1,344 | 4 |
| Case5 | 同Case4 x2 + Case3 x3 + Case2 x7 | | 4×6×6 |
## 预计算表格
**mod 64 表**:8 个特解 `min_sol64[8]`,通过遍历 x=1..15(奇数)构建。4 个解为 `x0, 32-x0, x0+32, 64-x0`。
**mod 729 表**:81 个特解 `min_sol729[81]`,通过遍历 x=1..364(非3倍数)构建。6 个解为 `x0, x0+243, x0+486, 729-x0, 729-x0-243, 729-x0-486`。
**mod 117649 表**:16807 个特解 `min_sol7[16807]`,通过遍历 x=1..58824(非7倍数)构建。6 个解通过乘以基解 `{1, 34967, 34968, 82681, 82682, 117648}` 再取模得到。
## 搜索裁剪
`searchUpTo_count` 搜索不超过 h_max 个 42 倍数,裁剪条件:
- **mod 7/8/9 裁剪**:rem % d > h_max 时剪枝(每个数的 6 次方 mod d 只能贡献 0 或 1)
- **下界裁剪**:rem < T[h_max] 时无解
- **上下界优化**:maxX = rem^(1/6), minX = (rem/h_max)^(1/6)
## 两个版本
| | l128dec_k6_lm.cpp | gmp2dec_k6_lm.cpp |
|---|---|---|
| 数据类型 | `__int128_t` | `mpz_class` (GMP) |
| m 范围 | ≤ ~38万(T数组溢出限制) | 理论无限 |
| 速度 | 快 | 较慢(GMP 开销) |
| 多线程 | OpenMP `schedule(dynamic)` | 同 |
## 已修复的 Bug(从 l128 同步到 GMP)
1. `initMod64Tables`:遍历范围 `x <= 7` → `x <= 15`
2. `getX64Candidates`:解公式 `x0+16, x0+32, x0+48` → `x0, 32-x0, x0+32, 64-x0`
3. `searchUpTo_count`:删除 `multiple` 参数,改用下界 `lb = (rem/h_max)^(1/6)` 优化
4. `searchCase` 参数类型:`ll` → `long`(模数值在 long 范围内)
5. 删除多线程中的 `ensureT` 调用(避免竞争)
## 性能参考(l128 版本)
| m 范围 | 时间 |
|--------|------|
| 10,000 | 0.13s |
| 20,000 | 0.79s |
| 40,000 | 3.8s |
| 60,000 | 12.3s |
| 100,000 | ~5min |
对应代码
- #include <iostream>
- #include <vector>
- #include <cmath>
- #include <algorithm>
- #include <cstdio>
- #include <gmpxx.h>
- using namespace std;
- typedef __int128_t ll;
- ll power6(ll x) {
- ll x2 = x * x;
- ll x4 = x2 * x2;
- return x4 * x2;
- }
- ostream& operator<<(ostream& os, ll n) {
- if (n == 0) return os << '0';
- if (n < 0) { os << '-'; n = -n; }
- char buf[64]; int i = 0;
- while (n > 0) { buf[i++] = char('0' + (n % 10)); n /= 10; }
- while (i--) os << buf[i];
- return os;
- }
- long power6_mod(ll x, long mod) {
- x %= mod;
- long x2 = (x * x) % mod;
- long x4 = (x2 * x2) % mod;
- return (x4 * x2) % mod;
- }
- ll ext_gcd(ll a, ll b, ll& x, ll& y) {
- if (b == 0) { x = 1; y = 0; return a; }
- ll g = ext_gcd(b, a % b, y, x);
- y -= a / b * x;
- return g;
- }
- ll crt_merge(ll r1, ll m1, ll r2, ll m2) {
- ll x, y;
- ll g = ext_gcd(m1, m2, x, y);
- if ((r2 - r1) % g != 0) return -1;
- ll M = m1 / g * m2;
- ll t1 = ((r2 - r1) / g) % (m2 / g);
- if (t1 < 0) t1 += (m2 / g);
- ll t2 = (x % (m2 / g));
- if (t2 < 0) t2 += (m2 / g);
- ll ans = (r1 + t1 * t2 % (m2 / g) * m1) % M;
- if (ans < 0) ans += M;
- return ans;
- }
- vector<ll> T;
- unsigned long T_max = 0;
- void initT(unsigned long maxVal) {
- T.resize(maxVal + 1);
- T[0] = 0;
- ll sum = 0;
- for (unsigned long i = 1; i <= maxVal; i++) {
- sum += power6((ll)i);
- T[i] = sum;
- }
- T_max = maxVal;
- }
- void ensureT(unsigned long maxVal) {
- if (maxVal <= T_max) return;
- T.resize(maxVal + 1);
- ll sum = (T_max > 0) ? T[T_max] : 0;
- for (unsigned long i = T_max + 1; i <= maxVal; i++) {
- sum += power6((ll)i);
- T[i] = sum;
- }
- T_max = maxVal;
- }
- int n;
- long M64 = 64, M729 = 729, M7 = 117649, M42_6;
- int min_sol64[8];
- int min_sol729[81];
- int min_sol7[16807];
- long sol7_base[6] = {1, 34967, 34968, 82681, 82682, 117648};
- void initMod64Tables() {
- for (int x = 1; x <= 15; x += 2) {
- long m6 = power6_mod(x, 64);
- int idx = (m6 - 1) / 8;
- min_sol64[idx] = x;
- }
- }
- void initMod729Tables() {
- for (int x = 1; x < 365; x++) {
- if (x % 3 == 0) continue;
- long m6 = power6_mod(x, 729);
- if (m6 % 9 == 1) {
- int idx = (m6 - 1) / 9;
- if (min_sol729[idx] == 0) min_sol729[idx] = x;
- }
- }
- }
- void initMod7Tables() {
- for (int x = 1; x < 58825; x++) {
- if (x % 7 == 0) continue;
- long m6 = power6_mod(x, M7);
- if (m6 % 7 == 1) {
- int idx = (m6 - 1) / 7;
- if (idx >= 0 && idx < 16807 && min_sol7[idx] == 0) min_sol7[idx] = x;
- }
- }
- }
- vector<long> getX64Candidates(long m6) {
- vector<long> xs;
- if (m6 == 0) {
- for (long x = 2; x < 64; x += 2) xs.push_back(x);
- } else if (m6 % 8 == 1) {
- int idx = (m6 - 1) / 8;
- long x0 = min_sol64[idx];
- xs.push_back(x0);
- xs.push_back(32 - x0);
- xs.push_back(x0 + 32);
- xs.push_back(64 - x0);
- }
- return xs;
- }
- vector<long> getX729Candidates(long m6) {
- vector<long> xs;
- if (m6 == 0) {
- for (long x = 3; x < 729; x += 3) xs.push_back(x);
- } else if (m6 % 9 == 1) {
- int idx = (m6 - 1) / 9;
- long x0 = min_sol729[idx];
- if (x0 == 0) return xs;
- xs.push_back(x0);
- xs.push_back(x0 + 243);
- xs.push_back(x0 + 486);
- xs.push_back(729 - x0);
- xs.push_back(729 - x0 - 243);
- xs.push_back(729 - x0 - 486);
- }
- return xs;
- }
- vector<long> findX7Candidates(long m6) {
- vector<long> xs;
- if (m6 == 0) {
- for (long x = 7; x < M7; x += 7) xs.push_back(x);
- } else if (m6 % 7 == 1) {
- int idx = (m6 - 1) / 7;
- long x0 = min_sol7[idx];
- if (x0 == 0) return xs;
- for (int i = 0; i < 6; i++) {
- long x = (x0 * sol7_base[i]) % M7;
- xs.push_back(x);
- }
- }
- return xs;
- }
- // Case 1: x2=x3=x7=x
- vector<long> generateCase1Candidates(long m6_mod64, long m6_mod729, long m6_mod7) {
- vector<long> cands64 = getX64Candidates(m6_mod64);
- vector<long> cands729 = getX729Candidates(m6_mod729);
- vector<long> cands7 = findX7Candidates(m6_mod7);
- vector<long> residues;
- for (long r64 : cands64) {
- for (long r729 : cands729) {
- ll r1 = crt_merge(r64, M64, r729, M729);
- if (r1 < 0) continue;
- for (long r7 : cands7) {
- ll r2 = crt_merge(r1, M64 * M729, r7, M7);
- if (r2 < 0) continue;
- residues.push_back((long)r2);
- }
- }
- }
- sort(residues.begin(), residues.end(), greater<ll>());
- return residues;
- }
- // Case 2: x23 (7 multiple) + x7 (6 multiple)
- vector<long> generateCase2x23Candidates(long m6_mod64, long m6_mod729) {
- vector<long> cands64 = getX64Candidates(m6_mod64);
- vector<long> cands729 = getX729Candidates(m6_mod729);
- ll M_x23 = M64 * M729;
- vector<long> residues;
- for (long r64 : cands64) {
- for (long r729 : cands729) {
- ll r = crt_merge(r64, M64, r729, M729);
- if (r < 0) continue;
- ll r7 = crt_merge(r, M_x23, 0, 7);
- if (r7 < 0) continue;
- residues.push_back((long)r7);
- }
- }
- sort(residues.begin(), residues.end(), greater<ll>());
- return residues;
- }
- vector<long> generateCase2x7Candidates(long m6_mod7) {
- vector<long> cands7 = findX7Candidates(m6_mod7);
- vector<long> residues;
- for (long r7 : cands7) {
- ll r = crt_merge(0, 6, r7, M7);
- if (r < 0) continue;
- residues.push_back((long)r);
- }
- sort(residues.begin(), residues.end(), greater<ll>());
- return residues;
- }
- // Case 3: x27 (3 multiple) + x3 (14 multiple)
- vector<long> generateCase3x27Candidates(long m6_mod64, long m6_mod7) {
- vector<long> cands64 = getX64Candidates(m6_mod64);
- vector<long> cands7 = findX7Candidates(m6_mod7);
- ll M_x27 = M64 * M7;
- vector<long> residues;
- for (long r64 : cands64) {
- for (long r7 : cands7) {
- ll r = crt_merge(r64, M64, r7, M7);
- if (r < 0) continue;
- ll r3 = crt_merge(r, M_x27, 0, 3);
- if (r3 < 0) continue;
- residues.push_back((long)r3);
- }
- }
- sort(residues.begin(), residues.end(), greater<ll>());
- return residues;
- }
- vector<long> generateCase3x3Candidates(long m6_mod729) {
- vector<long> cands729 = getX729Candidates(m6_mod729);
- vector<long> residues;
- for (long r729 : cands729) {
- ll r = crt_merge(0, 14, r729, M729);
- if (r < 0) continue;
- residues.push_back((long)r);
- }
- sort(residues.begin(), residues.end(), greater<ll>());
- return residues;
- }
- // Case 4: x37 (2 multiple) + x2 (21 multiple)
- vector<long> generateCase4x37Candidates(long m6_mod729, long m6_mod7) {
- vector<long> cands729 = getX729Candidates(m6_mod729);
- vector<long> cands7 = findX7Candidates(m6_mod7);
- ll M_x37 = M729 * M7;
- vector<long> residues;
- for (long r729 : cands729) {
- for (long r7 : cands7) {
- ll r = crt_merge(r729, M729, r7, M7);
- if (r < 0) continue;
- ll r2 = crt_merge(r, M_x37, 0, 2);
- if (r2 < 0) continue;
- residues.push_back((long)r2);
- }
- }
- sort(residues.begin(), residues.end(), greater<ll>());
- return residues;
- }
- vector<long> generateCase4x2Candidates(long m6_mod64) {
- vector<long> cands64 = getX64Candidates(m6_mod64);
- vector<long> residues;
- for (long r64 : cands64) {
- ll r = crt_merge(0, 21, r64, M64);
- if (r < 0) continue;
- residues.push_back((long)r);
- }
- sort(residues.begin(), residues.end(), greater<ll>());
- return residues;
- }
- // Case 5: x2 (21), x3 (14), x7 (6) all different
- vector<long> generateCase5x2Candidates( long m6_mod64) {
- return generateCase4x2Candidates( m6_mod64); // Same logic
- }
- vector<long> generateCase5x3Candidates( long m6_mod729) {
- return generateCase3x3Candidates(m6_mod729); // Same logic
- }
- vector<long> generateCase5x7Candidates( long m6_mod7) {
- return generateCase2x7Candidates( m6_mod7); // Same logic
- }
- bool searchUpTo_count(ll rem, int h_max, vector<ll>& xs, bool first_round=true) {
- if (rem == 0&&xs.size()>1) return true;
- if (h_max == 0) return false;
- if ((int)xs.size() >= n) return false;
- ll r8 = rem % 8;
- ll r9 = rem % 9;
- ll r7v = rem % 7;
- if (r8 > h_max) return false;
- if (r9 > h_max) return false;
- if (r7v > h_max) return false;
- if (h_max > 0 && (unsigned long)h_max <= T_max && rem < T[(unsigned long)h_max]) return false;
- ll prevX = first_round ? rem : xs.back();
- double ub = pow((double)rem, 1.0/6);
- long maxX = ceil(ub) + 1;
- while (maxX > 0 && power6(maxX) > rem) maxX--;
- if (maxX >= prevX) maxX = prevX - 1;
- double lb = pow((double)rem/h_max, 1.0/6);
- long minX = (long)ceil(lb);
- if (minX > maxX) return false;
- for (long x = maxX; x >= minX; x --) {
- ll x6 = power6(x);
- if (rem < x6) continue;
- xs.push_back(x);
- if (searchUpTo_count(rem - x6, h_max - 1, xs, false)) return true;
- if (rem == x6) return true;
- xs.pop_back();
- }
- return false;
- }
- bool searchCase(ll m, int case_num, long m6_mod64, long m6_mod729, long m6_mod7) {
- ll mk = power6(m);
- ll diff;
- ll rem;
- vector<ll> xs;
- if (case_num == 1) {
- vector<long> x_cands = generateCase1Candidates((long)m6_mod64, m6_mod729, m6_mod7);
- if (x_cands.empty()) return false;
- for (ll x_s : x_cands) {
- ll M6=5489031744L;
- for(ll x=x_s;x<m;x+=M6){
- ll x6 = power6(x);
- diff = mk - x6;
- if(diff<=0)break;
- if (diff % M42_6 != 0) {
- cerr<<"Error1\n";
- continue;
- }
- rem = diff / M42_6;
- xs.clear();
- xs.push_back(x);
- if (searchUpTo_count(rem, n - 1, xs)) {
- #pragma omp critical
- {
- cout << "FOUND Case1 m=" << m << ": ";
- for (ll xi : xs) cout << xi << " ";
- cout << endl;
- cout.flush();
- }
- return true;
- }
- }
- }
- }
- else if (case_num == 2) {
- vector<long> x23_cands = generateCase2x23Candidates(m6_mod64, m6_mod729);
- vector<long> x7_cands = generateCase2x7Candidates(m6_mod7);
- if (x23_cands.empty() || x7_cands.empty()) return false;
- ll M23=326592;
- for (ll x23_s : x23_cands) {
- for(ll x23 = x23_s;x23<m;x23+=M23){
- ll x23_6 = power6(x23);
- for (ll x7_s : x7_cands) {
- ll M7=705894L;
- for(ll x7=x7_s;x7<m;x7+=M7){
- if (x7 == x23) continue;
- ll x7_6 = power6(x7);
- diff = mk - x23_6 - x7_6;
- if(diff<0)break;
- if (diff % M42_6 != 0){
- cerr<<"Error2\n";
- continue;
- }
- rem = diff / M42_6;
- xs.clear();
- xs.push_back(x23);
- xs.push_back(x7);
- if (searchUpTo_count(rem, n - 2, xs)) {
- #pragma omp critical
- {
- cout << "FOUND Case2 m=" << m << ": ";
- for (ll xi : xs) cout << xi << " ";
- cout << endl;
- cout.flush();
- }
- return true;
- }
- }
- }
- }
- }
- }
- else if (case_num == 3) {
- vector<long> x27_cands = generateCase3x27Candidates(m6_mod64, m6_mod7);
- vector<long> x3_cands = generateCase3x3Candidates(m6_mod729);
- if (x27_cands.empty() || x3_cands.empty()) return false;
- for (ll x27_s : x27_cands) {
- ll M27=22588608L;
- for(ll x27=x27_s;x27<m;x27+=M27){
- ll x27_6 = power6(x27);
- for (ll x3_s : x3_cands) {
- ll M3=10206;
- for(ll x3=x3_s;x3<m;x3+=M3){
- if (x3 == x27) continue;
- ll x3_6 = power6(x3);
- diff = mk - x27_6 - x3_6;
- if(diff<0)break;
- if (diff % M42_6 != 0) {
- cerr<<"error3\n";
- continue;
- }
- rem = diff / M42_6;
- xs.clear();
- xs.push_back(x27);
- xs.push_back(x3);
- if (searchUpTo_count(rem, n - 2, xs)) {
- #pragma omp critical
- {
- cout << "FOUND Case3 m=" << m << ": ";
- for (ll xi : xs) cout << xi << " ";
- cout << endl;
- cout.flush();
- }
- return true;
- }
- }
- }
- }
- }
- }
- else if (case_num == 4) {
- vector<long> x37_cands = generateCase4x37Candidates(m6_mod729, m6_mod7);
- vector<long> x2_cands = generateCase4x2Candidates(m6_mod64);
- if (x37_cands.empty() || x2_cands.empty()) return false;
- for (ll x37_s : x37_cands) {
- ll M37=171532242L;
- for(ll x37=x37_s; x37<m; x37+=M37){
- ll x37_6 = power6(x37);
- for (ll x2_s : x2_cands) {
- ll M2=1344;
- for(ll x2=x2_s; x2<m;x2+=M2){
- if (x2 == x37) continue;
- ll x2_6 = power6(x2);
- diff = mk - x37_6 - x2_6;
- if(diff<0)break;
- if (diff % M42_6 != 0) {
- cerr<<"error4\n";
- continue;
- }
- rem = diff / M42_6;
- xs.clear();
- xs.push_back(x37);
- xs.push_back(x2);
- if (searchUpTo_count(rem, n - 2, xs)) {
- #pragma omp critical
- {
- cout << "FOUND Case4 m=" << m << ": ";
- for (ll xi : xs) cout << xi << " ";
- cout << endl;
- cout.flush();
- }
- return true;
- }
- }
- }
- }
- }
- }
- else if (case_num == 5) {
- vector<long> x2_cands = generateCase5x2Candidates(m6_mod64);
- vector<long> x3_cands = generateCase5x3Candidates(m6_mod729);
- vector<long> x7_cands = generateCase5x7Candidates(m6_mod7);
- if (x2_cands.empty() || x3_cands.empty() || x7_cands.empty()) return false;
- for (ll x2_s : x2_cands) {
- ll M2=1344;
- for(ll x2=x2_s;x2<m;x2+=M2){
- ll x2_6 = power6(x2);
- for (ll x3_s : x3_cands) {
- ll M3=10206;
- for(ll x3=x3_s;x3<m;x3+=M3){
- if (x3 == x2) continue;
- ll x3_6 = power6(x3);
- if(mk<x2_6+x3_6)break;
- for (ll x7_s : x7_cands) {
- ll M7=705894;
- for(ll x7=x7_s;x7<m;x7+=M7){
- if (x7 == x3 || x7==x2) continue;
- ll x7_6 = power6(x7);
- diff = mk - x2_6 - x3_6 - x7_6;
- if(diff<0)break;
- if (diff % M42_6 != 0) {
- cerr<<"error5\n";
- continue;
- }
- rem = diff / M42_6;
- xs.clear();
- xs.push_back(x2);
- xs.push_back(x3);
- xs.push_back(x7);
- if (searchUpTo_count(rem, n - 3, xs)) {
- #pragma omp critical
- {
- cout << "FOUND Case5 m=" << m << ": ";
- for (ll xi : xs) cout << xi << " ";
- cout << endl;
- cout.flush();
- }
- return true;
- }
- }
- }
- }
- }
- }
- }
- }
- return false;
- }
- bool is_primitive_candidate(ll m) {
- return (m % 2 != 0 && m % 3 != 0 && m % 7 != 0);
- }
- int main(int argc, char* argv[]) {
- if (argc < 4) {
- cerr << "Usage: " << argv[0] << " n m_start m_end" << endl;
- return 1;
- }
- time_t start=time(NULL);
- n = atoi(argv[1]);
- long m_start = atol(argv[2]);
- long m_end = atol(argv[3]);
- M42_6 = power6(42);
- printf("k=6 n=%d m_start=%ld m_end=%ld\n", n, (long)m_start, (long)m_end);
- printf("42^6 = %ld\n", (long)M42_6);
- initMod64Tables();
- initMod729Tables();
- initMod7Tables();
- long T_needed = m_end + 100;
- initT((unsigned long)T_needed);
- printf("initT done, T_max=%lu\n", T_max);
- bool found=false;
- long minm=-1;
- #pragma omp parallel for schedule(dynamic)
- for (long m = m_start; m <= m_end; m++) {
- if (!is_primitive_candidate(m)) continue;
- long m6_mod64 = power6_mod(m, 64);
- long m6_mod729 = power6_mod(m, 729);
- long m6_mod7 = power6_mod(m, M7);
- for (int case_num = 1; case_num <= 5; case_num++) {
- if(searchCase(m, case_num, m6_mod64, m6_mod729, m6_mod7)){
- #pragma omp critical
- {
- {
- found=true;
- if(minm<0||m<minm){
- minm=m;
- }
- }
- }
- }
- }
- if(m%100==1)
- #pragma omp critical
- {
- long diff = time(NULL) -start;
- cerr<<"m="<<m<<" processed cost "<<diff<<"s\n";
- cerr.flush();
- }
- }
- if(!found){
- cout << "NO_SOLUTION in range" << endl;
- }else{
- cout << "Found best m = "<<minm<<endl;
- }
- return 1;
- }
复制代码 |
|