寻找使n^2-n+11素因子个数不少于k的最小正整数n
令$f(n)=n^2-n+11$,如何快速找到使f(n)素因子个数（可以重复）不少于k的最小正整数n？我想到的两个办法一是直接从n=1开始穷举，这个方法算到k=12算不动了，n>43864513.
第二个办法是利用n^2-n+11的素因子p满足-43是p的二次剩余，从而p属于集合$g={11, 13, 17, 23, 31, 41, 47, 53, 59, 67, 79, 83, 97, 101, 103, 107, 109,\cdots}$
这样从g中选择k个数（可重复）相乘得到a，然后测试4a-43是否为完全平方数。这样做最主要的难点是如何做到从小到大地选取乘积a。
k<12的时候对应的n和f(n)以及f(n)的因式分解：
{1,1,{{11,1}}}
{2,11,{{11,2}}}
{3,54,{{13,2},{17,1}}}
{4,132,{{11,3},{13,1}}}
{5,561,{{11,1},{13,4}}}
{6,2794,{{11,4},{13,1},{41,1}}}
{7,14510,{{11,3},{13,1},{23,3}}}
{8,48895,{{11,2},{13,3},{17,1},{23,2}}}
{9,568206,{{11,5},{13,1},{17,1},{47,1},{193,1}}}
{10,2826979,{{11,1},{13,5},{17,1},{31,1},{47,1},{79,1}}}
{11,10866416,{{11,5},{13,2},{23,2},{59,1},{139,1}}}
可以看到除了k=3以外其他的f(n)都能被11整除，我想扩大范围看看有没有其他的反例。 我试验了一下，用第二种方法优势也不大，主要需要穷举n^2-n+11的所有可能因子分解情况，这个数范围比较大（虽然我们只要检查其中稀疏的部分）
我的计算机计算到10个因子的情况，已经使用了5.5G左右的内存
n=192844433有12个因子，对应$n^2-n+11=11xx13^6xx17xx31xx67xx83xx239$
n=878135105结果有13个因子，对应$n^2-n+11=11^7xx17xx23xx31^2xx53xx1987$
显然对于因子越多的数，其小因子出现的概率会越大，所以总是有11也不奇怪
14个因子的可以找到n=3609076912,
15个因子可以搜索到n=34625156643，这里开始都不确保是最小的
16个因子可以搜索到n=193282953996
17个因子可以搜索到n=410573993390
18个因子可以搜索到n=8337163994886
19个因子可以搜索到n=38474341378892
20个因子可以搜索到n=370947905947894
页:
[1]