马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。
您需要 登录 才可以下载或查看,没有账号?欢迎注册
×
令$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整除,我想扩大范围看看有没有其他的反例。 |