如题,这是一个数学证明题。对是我乱想的。
形式化地(我乱学的LaTeX好丑陋): ∀m∈N,∃N∈N,∀x≥N,∃K={k1,...,km},{∀a∈K,isprime(a)=false}∧∑i=1mki=x∧{∀a,b∈K∧a=b,gcd(a,b)=1}
对于 m=2 ,可以证明 N=210 时上述命题成立,且 210 是 N 可取的最小值。具体证明用了 ϕ(n) 与 π(n) 之间的关系,即转化为求证 ϕ(n)>2π(n) 。这个式子可以用一些高级的放缩来整,是我之前求助一个大佬搞的 (orz)。
现在将 m 拓展到任意3及以上的正整数,这个命题仍成立吗?
下面有一段我用于分析 m=3 和 m=4 的情况的代码(也是为什么我会把这帖发在洛谷上):
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
#include<set>
#include<deque>
using namespace std;
typedef unsigned int UI;
const UI N = 65536;
UI subs[N], ntps[N];
bool ntp[N];
UI l = 0, r = 0, q = 0;
UI gcd(UI a, UI b)
{
if(!(a && b))
{
cerr << "ERROR\n";
return 0;
}
while(a = a % b)swap(a, b);
return b;
}
void ask(UI m)
{
for(UI i = 0; ntps[i] <= m - 34; ++i)
{
for(UI j = i + 1; ntps[j] <= m - 25 - ntps[i]; ++j)
{
UI k = m - ntps[i] - ntps[j];
if(ntp[k] && gcd(ntps[i], ntps[j]) == 1 && gcd(ntps[i], k) == 1 &&
gcd(ntps[j], k) == 1)
{
if(ntps[i] != 4 && ntps[i] != 9)
cout << ntps[i] << ' ' << ntps[j] << ' ' << k << ' ' << m << endl;
goto end;
}
}
}
cout << "impossible for " << m << endl;
end:;
}
int main(int argc, char* argv[])
{
for(UI i = 2; i < sqrt(N); ++i)
{
if(ntp[i])continue;
for(UI j = 2; j != (N + i - 1) / i; ++j)ntp[i * j] = true;
}
//for(UI i = 0; i != N; ++i)cout << ntp[i] << ' ';
for(UI i = 0, j = 0; i != N; ++i)
{
if(ntp[i])ntps[j++] = i;
}
while(true)
{
cin >> l >> r;
l = max(l, (UI)38);
for(UI i = l; i <= r; ++i)
{
ask(i);
}
cout << "next?(+x=next, 0=exit)\n";
cin >> q;
if(!q)break;
}
return 0;
}
//min possible = 38, max impossible = 175
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
#include<set>
#include<deque>
using namespace std;
typedef unsigned int UI;
const UI N = 65536;
UI subs[N], ntps[N];
bool ntp[N];
UI l = 0, r = 0, q = 0;
UI gcd(UI a, UI b)
{
if(!(a && b))
{
cerr << "ERROR\n";
return 0;
}
while(a = a % b)swap(a, b);
return b;
}
void ask(UI m)
{
for(UI i = 0; ntps[i] <= m - 83; ++i)
{
for(UI j = i + 1; ntps[j] <= m - 79 - ntps[i]; ++j)
{
for(UI k = j + 1; ntps[k] <= m - 70 - ntps[i] - ntps[j]; ++k)
{
UI l = m - ntps[i] - ntps[j] - ntps[k];
if(ntp[l] &&
gcd(ntps[i], ntps[j]) == 1 &&
gcd(ntps[i], ntps[k]) == 1 &&
gcd(ntps[i], l) == 1 &&
gcd(ntps[j], ntps[k]) == 1 &&
gcd(ntps[j], l) == 1 &&
gcd(ntps[k], l) == 1)
{
if(ntps[i] != 4 && ntps[i] != 9)
cout << ntps[i] << ' ' << ntps[j] << ' ' << ntps[k] << ' ' <<
l << ' ' << m << endl;
goto end;
}
}
}
}
cout << "impossible for " << m << endl;
end:;
}
int main(int argc, char* argv[])
{
for(UI i = 2; i < sqrt(N); ++i)
{
if(ntp[i])continue;
for(UI j = 2; j != (N + i - 1) / i; ++j)ntp[i * j] = true;
}
//for(UI i = 0; i != N; ++i)cout << ntp[i] << ' ';
for(UI i = 0, j = 0; i != N; ++i)
{
if(ntp[i])ntps[j++] = i;
}
while(true)
{
cin >> l >> r;
l = max(l, (UI)38);
for(UI i = l; i <= r; ++i)
{
ask(i);
}
cout << "next?(+x=next, 0=exit)\n";
cin >> q;
if(!q)break;
}
return 0;
}
这两段代码显然是分开的,前面计算 m=3 ,后面是 m=4 ,结果都不大(前者我注释了,后者我没注释但记得是五百多)
第一次发学术版,没怎么深入研究这个问题,请各路大佬多多包涵。如果这个猜想已经在学术界被研究了,还望请指个路;如果本贴某些内容有(非(违法违规或违反相关规定)的问题,请联系我,我会尽快改正。