被连续自然数取模后全为质数的最小整数
求一个大于2的最小整数，其被$3，4，5，6，7，..., n-1, n$ 除后余数都是质数。经过代码验证：
n=4，最小整数是 11，
n=5~10，最小整数是 23，
n=11~12，最小整数是 47，
n=13~24，最小整数是 887，
n=25~28，最小整数是 39107，
n=29~30，最小整数是 503627，
n=31~34，最小整数是1021907，
n=35~36，最小整数是 11088227，
n=37~40，最小整数是 12649367，
n=41~43，最小整数是 103424807，
n=44，最小整数是 2860681127，
n=45~48，最小整数是 3383683607，
n=49~50，最小整数是 8261017607
n=51~52，最小整数是 188008585607
n=53~56,最小整数是 1395515070407
n=57~58,最小整数是 2345173940567
n=59~60,最小整数是 3018245755367
n=61~62,最小整数是 7985415341207
11#
63 1479414399394932002
64~66 2690526997513555202
67~706173829500412974402
71~72 40167003465777988802
73 68441507929450656002
74~78 195797066175538027202
79~81616072054588129339202
82 11689927965263544796802
83~85 200413348268577717873602
86~88 1300882803083249632646402
89~93 2471436184401308960035202
94~96 425002077871009060888065602
97 562356157505626272053865602
98~100 1673620390251025045311081602
101~102 2034287189655174142001913602
103~105 6497642650272411454440624002
106~108 293794470445062408741351432002
12#
109~112 63316341740975305645497774139202
113~117 315317221876783126525319154360002
118~121 359391980206726313623343310744002
122~124 173044793183066045276433017693673602
125~126 393565946202528402313011298817520002
127~130 4437387269491025869779373423874064002
131~133 26628491970767443062229473376178352002
134~138 259613540181287584989772406543516304002
21#
139~141 4188696294935413706934768125377042512002
142~150 71375535419096138855747944430720887776002
151~156 28466105341303483745606123156025578668368002
157 81849859751405924059843476855289279826496002
158~162 746294017377509464097706103446488143037568002
163~165 33635406647457932883180477167488271261164992002
166 154918018148228242519886464835636651505317472002
167~168 299084197184085790849033982186295000595719696002
169~172 3531371825353917671492584999407565716875889792002
23#
173~177 116810701936766586361368933161051719437728630688002
178 353943738186338730051340043852386052151622936272002
179~180 7459558178581420991908368303782280420035186413104002
181~190 26079504486542128214527139484976208504732884352208002
191~192 114397711072547200623926739913773332504663121492864002
193~196 7333244963252694316979523001920058246398799258689312002
197~198 16754955673880622369079802324257242816195831706070400002
199~205 1241815872795527340920909004524886711949273374627222000002
206~210 72225715647186222395152227158525640349057726424522471280002
211~213 85659367391722784092607464197468049651961443566063782640002
214~217 31673053784774069114917859005213870009008990233082429871008002
218~222 663127145086112525715369034835863236326107289562909156940992002
223~225 2036184500294580388401873354629853515994924364902165172748112002
226~232 185768755747358998327069097333443876936859437235420585132525904002
233~241 4828299556190106737188708726420164405880642740182586600077808144002
242~250 1439011990188211741334841754244394476887612560371605459101394720656002
几年前想过类似问题
可能只有搜索一条路
因为如果，我们稍微一般化一些，把问题改成，这里有若干重复0-1序列
0 1 0 0 1 0……(循环周期为3)
0 1 0 0 0 1 0 0……(循环周期为4)
0 1 0 0 0 0 1 0 0 0……(循环周期为5)
0 1 0 0 1 0 0 1 0 0 1 0……(循环周期为6)
0 1 0 0 1 0 0 0 1 0 0 1 0 0……(循环周期为7)
0 1 0 0 1 0 1 0 0 1 0 0 1 0 1 0……(循环周期为8)
……
问这些循环序列什么时候同时取1
这个问题是你的问题的推广（只要把循环序列的起点改改位置，忽略掉前两位0 1，就是你的问题的等价问题）
而如果没记错，RSA可以化归成这个推广
我曾经讨论过这个推广问题，但好像没有答案
https://bbs.emath.ac.cn/thread-15495-1-1.html
让我想想当初我是怎么化归的好了
没记错是转去二次剩余
对n=pq,计算s^2%n, 得到r
从而r同时是p和q的二次剩余
根据二次互反律，我们可以r，推得p和q是某些小素数的二次剩余/二次非剩余（忘记这里怎么化简了）
然后把小素数的二次剩余列成循环0-1序列，借助上面提到的算法，就能进行计算了
大概如此
当然不排除几年前脑子抽筋忘记s^2%n很大的这个事实 找出一些特别约束
2(Mod 3)
3(Mod 4)
5(Mod 6)
11(Mod 12)
2(Mod 15)
17(Mod 30)
2(Mod 45)
47(Mod 60)
47(Mod 90)
47(Mod 120)
2(Mod 135)
3(Mod 140)
17(Mod 150)
2(Mod 165)
47(Mod 180)
17(Mod 210)
2(Mod 225)
11(Mod 228)
167(Mod 240)
137(Mod 270)
3(Mod 280)
167(Mod 300)
2(Mod 315)
59(Mod 336)
47(Mod 360)
167(Mod 390)
2(Mod 405)
11(Mod 456)
167(Mod 480)
2(Mod 495)
47(Mod 510)
17(Mod 570)
2(Mod 585)
47(Mod 588)
167(Mod 600)
2(Mod 675)
11(Mod 684)
17(Mod 690)
3(Mod 700)
167(Mod 780)
11(Mod 816)
2(Mod 855)
17(Mod 870)
3(Mod 910)
11(Mod 912)
17(Mod 930)
2(Mod 945)
647(Mod 960)
3(Mod 980) 前面我认为最小结果不可能是偶数，因为如果是，那么必然会导致这个结果超级大，但是发现去除偶数条件后，得出上面的列表中
11(Mod 12)
2(Mod 15)
3(Mod 140)
会存在矛盾，也就是140以后，只能为偶数并且模所有范围内偶数为2 现在去除结果必须是偶数的额外要求，那么关于各个n,1000以内余数唯一的有:
2(Mod 3)
2(Mod 15)
2(Mod 45)
2(Mod 132) #说明n在132以后，结果只能取偶数, 而且除以任意不超过132（但是大于2）的偶数的余数都是2.
2(Mod 135)
2(Mod 165)
2(Mod 225)
2(Mod 264)
2(Mod 315)
2(Mod 330)
2(Mod 396)
2(Mod 405)
2(Mod 420)
2(Mod 450)
2(Mod 495)
2(Mod 528)
2(Mod 540)
2(Mod 585)
2(Mod 630)
2(Mod 660)
2(Mod 672)
2(Mod 675)
2(Mod 720)
2(Mod 792)
2(Mod 810)
2(Mod 840)
2(Mod 855)
2(Mod 900)
2(Mod 924)
2(Mod 945)
2(Mod 990)
余数只有两个的有
(Mod 4)
(Mod 5)
(Mod 6)
(Mod 9)
(Mod 12)
(Mod 30)
(Mod 60)
(Mod 75)
(Mod 90)
(Mod 105)
(Mod 120)
(Mod 140)
(Mod 150)
(Mod 180)
(Mod 195)
(Mod 210)
(Mod 228)
(Mod 240)
(Mod 255)
(Mod 270)
(Mod 280)
(Mod 285)
(Mod 300)
(Mod 336)
(Mod 345)
(Mod 360)
(Mod 390)
(Mod 435)
(Mod 456)
(Mod 465)
(Mod 480)
(Mod 510)
(Mod 525)
(Mod 561)
(Mod 570)
(Mod 588)
(Mod 600)
(Mod 615)
(Mod 627)
(Mod 684)
(Mod 690)
(Mod 693)
(Mod 700)
(Mod 735)
(Mod 765)
(Mod 780)
(Mod 816)
(Mod 819)
(Mod 825)
(Mod 870)
(Mod 910)
(Mod 912)
(Mod 930)
(Mod 960)
(Mod 975)
(Mod 980)
余数只有三个的有
(Mod 7)
(Mod 8)
(Mod 10)
(Mod 14)
(Mod 18)
(Mod 20)
(Mod 21)
(Mod 24)
(Mod 28)
(Mod 33)
(Mod 36)
(Mod 42)
(Mod 44)
(Mod 48)
(Mod 66)
(Mod 70)
(Mod 84)
(Mod 99)
(Mod 176)
(Mod 198)
(Mod 204)
(Mod 231)
(Mod 273)
(Mod 375)
(Mod 408)
(Mod 429)
(Mod 455)
(Mod 462)
(Mod 520)
(Mod 532)
(Mod 546)
(Mod 555)
(Mod 560)
(Mod 572)
(Mod 576)
(Mod 624)
(Mod 645)
(Mod 665)
(Mod 704)
(Mod 715)
(Mod 750)
(Mod 759)
(Mod 805)
(Mod 836)
(Mod 858)
(Mod 880)
(Mod 915)
(Mod 957)
而对于小于132的情况，我们可以先仅搜索奇数的结果，这时结果只有一种的有
3 (Mod 4)
5 (Mod 6)
11 (Mod 12)
2 (Mod 15)
17 (Mod 30)
2 (Mod 45)
47 (Mod 60)
47 (Mod 90)
47 (Mod 120)
两种的有
(Mod 5)
(Mod 8)
(Mod 9)
(Mod 10)
(Mod 14)
(Mod 18)
(Mod 20)
(Mod 24)
(Mod 28)
(Mod 36)
(Mod 42)
(Mod 44)
(Mod 48)
(Mod 66)
(Mod 70)
(Mod 75)
(Mod 84)
(Mod 105)
三种的有:
(Mod 7)
(Mod 16)
(Mod 21)
(Mod 33)
(Mod 40)
(Mod 78)
(Mod 88)
(Mod 96)
(Mod 99)
(Mod 126)
(Mod 130)
本帖最后由 .·.·. 于 2020-8-5 23:31 编辑
在mathe的启发下……我发现
这个预搜索指令真心好用：
LENGTH=7200;
b=Vec(0,LENGTH);
for(i=1,LENGTH,b=i)
fordiv(LENGTH,t,if(t>2 && t<=50,c=[];for(i=1,length(b),if(!isprime(b%t),c=setunion(c,)));b=setminus(b,c)))
b换成Rust代码（因为setunion步在LENGTH很大时候太耗时，而我不知道如何操作gp的Vec）fn search_pre(){
let mut b:Vec<_>=(1..=LENGTH).collect();
for t in 3..=UPPER{
if LENGTH%t==0{
for i in (0..b.len()).rev(){
if !ISPRIME{b.swap_remove(i);}
}
}
}
b.sort_unstable();
println!("{} {:?}",LENGTH,b);
}得到
1058400
这样我们可以很方便地进行搜索了
等我结果~
本帖最后由 .·.·. 于 2020-8-6 02:06 编辑
.·.·. 发表于 2020-8-5 22:54
在mathe的启发下……我发现
这个预搜索指令真心好用：
换成Rust代码（因为setunion步在LENGTH很大时候太 ...
23:39:56> for(i=3,65,if(!isprime(3018245755367%i),print(i)))
61
63
64
23:40:08> for(i=3,65,if(!isprime(3881604836567%i),print(i)))
61
63
65
23:40:22> for(i=3,65,if(!isprime(7985415341207%i),print(i)))
63
65
23:40:31> for(i=3,65,if(!isprime(8349851234567%i),print(i)))
63
用60测得的4个结果，最小的3018245755367会在61失效，而直到n=62，7985415341207仍然可用
算这个……
real 0m2.583s
user 0m24.142s
sys 0m0.076s
Rust是个好程序
预计算是个好算法
#!
const ISPRIME:=;
const UPPER:usize=60;
extern crate rayon;
use rayon::prelude::*;
fn main(){
let b=search_pre();
search_after(&b);
}
const LENGTH:usize=2usize.pow(5)*3usize.pow(3)*5usize.pow(2)*7usize.pow(2);
fn search_pre()->Vec<usize>{
let mut b:Vec<_>=(1..=LENGTH).collect();
for t in 3..=UPPER{
if LENGTH%t==0{
for i in (0..b.len()).rev(){
if !ISPRIME%t]{b.swap_remove(i);}
}
}
}
b.sort_unstable();
b
}
fn search_after(b:&){
(0..8000000usize).into_par_iter().for_each(|x|{
for i in b.into_iter().map(|c|c+x*LENGTH){
if (3..=UPPER).all(|t|ISPRIME){
println!("found n={}!",i)
}
}
})
}
下面可以放心地从搜索63开始了
Update：63的结果：
found n=2!
found n=5117373107443396802!
found n=5469140162292206402!
found n=4561419428803036802!
found n=12698992845016077602!
found n=15055225617580948802!
found n=3364025168209305602!
found n=1479414399394932002!
62的时候最小值是7985415341207
63的时候最小值是1479414399394932002
害怕……
PS.n>=63时，数字mod1010824870255200的结果只能是2,288807105787202,577614211574402
这里1010824870255200是CRT算出来的
把Rust改成u128之后算得
00:45:21> for(i=3,90,if(!isprime(195797066175538027202%i),print(i);break))
79
00:45:38> for(i=3,90,if(!isprime(616072054588129339202%i),print(i);break))
81Rust主程序如下
#!
const ISPRIME:=;
const UPPER:usize=74;
const LENGTH:u128=if UPPER>=63 {1010824870255200} else{2usize.pow(5)*3usize.pow(3)*5usize.pow(2)*7usize.pow(2)} as u128;
extern crate rayon;
use rayon::prelude::*;
fn main(){
let b=if UPPER<63{
search_pre()
}else{
search_pre_ge63()
};
search_after(&b);
}
fn search_pre()->Vec<u128>{
dbg!(LENGTH);
let mut b:Vec<_>=(1..=LENGTH).collect();
for t in 3..=UPPER as u128{
if LENGTH%t==0{
for i in (0..b.len()).rev(){
if !ISPRIME[(b%t) as usize]{b.swap_remove(i);}
}
}
}
b.sort_unstable();
dbg!(b)
}
fn search_pre_ge63()->Vec<u128>{
assert!(LENGTH==1010824870255200);
vec!
}
fn search_after(b:&){
(0..3193600u128).into_par_iter().for_each(|x|{
for i in b.into_iter().map(|c|c+x*LENGTH){
if (3..=UPPER).all(|t|ISPRIME[(i%t as u128) as usize]){
println!("found n={}!",i)
}
}
})
}
Update，如果我的搜索没错（多半有BUG……）
n=63时，每rep=591133442051411133755680800个数中有294053760个数符合题意
本帖最后由 .·.·. 于 2020-8-6 03:33 编辑
果然，内存就是正义~
总计 已用 空闲 共享 缓冲/缓存 可用
内存： 62Gi 20Gi 29Gi 511Mi 12Gi 41Gi
交换： 0B 0B 0B
Finished release target(s) in 1.06s
Running `target/release/rayonops`
i=37,len=33,rep=37400520199442400
i=41,len=396,rep=1533421328177138400
i=43,len=5148,rep=65937117111616951200
i=47,len=72072,rep=3099044504245996706400
i=53,len=1081080,rep=164249358725037825439200
i=59,len=17297280,rep=9690712164777231700912800
i=61,len=294053760,rep=591133442051411133755680800
found n=3364025168209305602!
found n=3364025168209305602!
found n=3364025168209305602!
found n=51028461100223006402!
found n=51028461100223006402!
found n=51028461100223006402!
found n=51028461100223006402!
found n=68441507929450656002!
found n=68441507929450656002!
found n=68441507929450656002!
found n=195797066175538027202!
found n=195797066175538027202!
found n=195797066175538027202!
found n=195797066175538027202!
found n=195797066175538027202!
found n=616072054588129339202!
found n=616072054588129339202!
found n=8410148118619471224002!
found n=200413348268577717873602!
found n=200413348268577717873602!
found n=200413348268577717873602!
found n=200413348268577717873602!
found n=2471436184401308960035202!
found n=2471436184401308960035202!
found n=2471436184401308960035202!
found n=2471436184401308960035202!
found n=2471436184401308960035202!
found n=2471436184401308960035202!
found n=2471436184401308960035202!
found n=2471436184401308960035202!
real 8m40.586s
user 8m32.632s
sys 0m6.895s
用的n=63做初次筛选，n=63的第一个循环周期中，最好结果是n=93:2471436184401308960035202
调整参数从94开始搜索，至106
程序
#!
const ISPRIME:=;
fn main(){
let mut x=(vec!,442720643463713815200);
for i in 48..=70{
x=search_roll(x.0,i,x.1);
println!("i={},len={},rep={}",i,(x.0).len(),x.1)
}
(x.0).sort_unstable();
search_once(&x.0);
}
#
fn gcd(mut i:u128,mut j:u128)->u128{//ensure i<j for better performance
while i != 0{
let t=j%i;
j=i;
i=t;
}
j
}
fn search_roll(b:Vec<u128>,ix:u128,mut repeats:u128)->(Vec<u128>,u128){
let i=ix/gcd(ix,repeats);
let mut b=if i>1{b.into_iter().map(|x|(0..i).map(|c|c*repeats+x).collect::<Vec<_>>()).flatten().collect::<Vec<_>>()}else{b};
repeats*=i;
for i in (0..b.len()).rev(){
if !ISPRIME[(b%ix) as usize]{b.swap_remove(i);}
}
(b,repeats)
}
fn search_once(b:&){
let mut upper=94;
let mut c=b.into_iter();
c.next();
for i in c{
while (94..=upper).all(|t|ISPRIME[(i%t as u128) as usize]){
upper+=1;
println!("found n={}!",i)
}
}
}
结果
$ time cargo run --release
Compiling rayonops v0.1.0 (/me/rust/rayonops)
Finished release target(s) in 0.40s
Running `target/release/rayonops`
i=48,len=1,rep=442720643463713815200
i=49,len=3,rep=3099044504245996706400
i=50,len=3,rep=3099044504245996706400
i=51,len=3,rep=3099044504245996706400
i=52,len=3,rep=3099044504245996706400
i=53,len=45,rep=164249358725037825439200
i=54,len=45,rep=164249358725037825439200
i=55,len=45,rep=164249358725037825439200
i=56,len=45,rep=164249358725037825439200
i=57,len=45,rep=164249358725037825439200
i=58,len=45,rep=164249358725037825439200
i=59,len=720,rep=9690712164777231700912800
i=60,len=720,rep=9690712164777231700912800
i=61,len=12240,rep=591133442051411133755680800
i=62,len=12240,rep=591133442051411133755680800
i=63,len=12240,rep=591133442051411133755680800
i=64,len=12240,rep=1182266884102822267511361600
i=65,len=12240,rep=1182266884102822267511361600
i=66,len=12240,rep=1182266884102822267511361600
i=67,len=220320,rep=79211881234889091923261227200
i=68,len=220320,rep=79211881234889091923261227200
i=69,len=220320,rep=79211881234889091923261227200
i=70,len=220320,rep=79211881234889091923261227200
found n=347092984475551631116802!
found n=347092984475551631116802!
found n=347092984475551631116802!
found n=347092984475551631116802!
found n=347092984475551631116802!
found n=347092984475551631116802!
found n=347092984475551631116802!
found n=3656872515010276113552002!
found n=3656872515010276113552002!
found n=3656872515010276113552002!
found n=3656872515010276113552002!
found n=3656872515010276113552002!
found n=438874286513301069573542402!
found n=2945647999374828361426612802!
found n=2945647999374828361426612802!
found n=15928574310436718235442737602!
found n=15928574310436718235442737602!
found n=15928574310436718235442737602!
found n=15928574310436718235442737602!
real 0m1.012s
user 0m1.390s
sys 0m0.077s
$ time cargo run --release
Compiling rayonops v0.1.0 (/me/rust/rayonops)
Finished release target(s) in 0.42s
Running `target/release/rayonops`
(2..HALF).fold(1, |s, x| s * (x / gcd(s, x))) = 164249358725037825439200
i=54,len=1,rep=164249358725037825439200
i=55,len=1,rep=164249358725037825439200
i=56,len=1,rep=164249358725037825439200
i=57,len=1,rep=164249358725037825439200
i=58,len=1,rep=164249358725037825439200
i=59,len=16,rep=9690712164777231700912800
i=60,len=16,rep=9690712164777231700912800
i=61,len=272,rep=591133442051411133755680800
i=62,len=272,rep=591133442051411133755680800
i=63,len=272,rep=591133442051411133755680800
i=64,len=272,rep=1182266884102822267511361600
i=65,len=272,rep=1182266884102822267511361600
i=66,len=272,rep=1182266884102822267511361600
i=67,len=4896,rep=79211881234889091923261227200
i=68,len=4896,rep=79211881234889091923261227200
i=69,len=4896,rep=79211881234889091923261227200
i=70,len=4896,rep=79211881234889091923261227200
i=71,len=93024,rep=5624043567677125526551547131200
i=72,len=93024,rep=5624043567677125526551547131200
i=73,len=1860480,rep=410555180440430163438262940577600
found number=7428738981146675284850822064002 for n=107!
found number=7428738981146675284850822064002 for n=108!
found number=63316341740975305645497774139202 for n=109!
found number=63316341740975305645497774139202 for n=110!
found number=63316341740975305645497774139202 for n=111!
found number=63316341740975305645497774139202 for n=112!
found number=315317221876783126525319154360002 for n=113!
found number=315317221876783126525319154360002 for n=114!
found number=315317221876783126525319154360002 for n=115!
found number=315317221876783126525319154360002 for n=116!
found number=315317221876783126525319154360002 for n=117!
found number=359391980206726313623343310744002 for n=118!
found number=359391980206726313623343310744002 for n=119!
found number=359391980206726313623343310744002 for n=120!
found number=359391980206726313623343310744002 for n=121!
real 0m14.928s
user 0m15.362s
sys 0m0.093s
$ time cargo run --release
Compiling rayonops v0.1.0 (/me/rust/rayonops)
Finished release target(s) in 0.42s
Running `target/release/rayonops`
(2..HALF).fold(1, |s, x| s * (x / gcd(s, x))) = 591133442051411133755680800
i=62,len=1,rep=591133442051411133755680800
i=63,len=1,rep=591133442051411133755680800
i=64,len=1,rep=1182266884102822267511361600
i=65,len=1,rep=1182266884102822267511361600
i=66,len=1,rep=1182266884102822267511361600
i=67,len=18,rep=79211881234889091923261227200
i=68,len=18,rep=79211881234889091923261227200
i=69,len=18,rep=79211881234889091923261227200
i=70,len=18,rep=79211881234889091923261227200
i=71,len=342,rep=5624043567677125526551547131200
i=72,len=342,rep=5624043567677125526551547131200
i=73,len=6840,rep=410555180440430163438262940577600
i=74,len=6840,rep=410555180440430163438262940577600
i=75,len=6840,rep=410555180440430163438262940577600
i=76,len=6840,rep=410555180440430163438262940577600
i=77,len=6840,rep=410555180440430163438262940577600
i=78,len=6840,rep=410555180440430163438262940577600
i=79,len=143640,rep=32433859254793982911622772305630400
i=80,len=143640,rep=32433859254793982911622772305630400
i=81,len=287280,rep=97301577764381948734868316916891200
i=82,len=287280,rep=97301577764381948734868316916891200
i=83,len=6320160,rep=8076030954443701744994070304101969600
found number=173044793183066045276433017693673602 for n=122!
found number=173044793183066045276433017693673602 for n=123!
found number=173044793183066045276433017693673602 for n=124!
found number=393565946202528402313011298817520002 for n=125!
found number=393565946202528402313011298817520002 for n=126!
found number=4437387269491025869779373423874064002 for n=127!
found number=4437387269491025869779373423874064002 for n=128!
found number=4437387269491025869779373423874064002 for n=129!
found number=4437387269491025869779373423874064002 for n=130!
real 1m11.578s
user 1m11.703s
sys 0m0.164s
算131的时候u128溢出了，而Rust没有u256供我使用
就这样吧
n=63就提前进入偶数了?非常意外。进入偶数范围后会要求对所有范围内偶数余数为2，这个条件非常厉害，会一下子大大缩小范围 的确，通过寻找166320的因子作为标准，如果仅查看奇数情况，那么得出
在n=62时，模166320只留下余数69527和124967
而继续添加n=63时，模166320已经没有任何余数留下了，这说明n=63以后的结果必然是偶数。
于是结果模62以下所有偶数都是2,由此得出结果Mod(2, 144403552893600)
于是n=63的结果必然形如144403552893600*k+2,而且关于32到63之间任意一个素数或素数的幂的余数都是素数
于是可以搜索到k=10245时，结果1479414399394932002满足