挑战R509分解

数论爱好者

有一个网站https://stdkmd.net/nrr/repunit/
专门研究了:分解c=(10^n-1)/9,这里的n限制为质数.我对其中的部分分解类型感兴趣.这类数中有一个极小类型,太难以分解,通常只能分解成两个因子x和y.举例:n=5,c是5位数,因子规律:x值(2位)+y值(3位)=5(n值),x值具有2*n*k+1=2*5*4+1=41的形式,y值具有2*n*m+1=2*5*27+1=271的形式,c=(10^5-1)/9=41*271.
n=7,c是7位数,因子规律:x值(3位)+y值(4位)=7(n值),x值具有2*n*k+1=2*7*17+1=239的形式,y值具有2*n*m+1=2*7*332+1=4649的形式.c=(10^7-1)/9=239*4649.
n=11时规律相同.
今天要挑战的难题是:c=(10^509-1)/9,这个数经严格判定为合数,经过长时间分解,没有找到任何因子,我猜属于只有两个因子的情形,x值254位,y值255位.你们帮忙分析一下,有没有更好的补充条件,最终分解这个大数
经过部分数据观察:x值大于sqrt(10^((n-1)/2) +1)
单n=5时,(5-1)/2+1=3,此时sqrt(10^3)=31.6, 41大于31.6
单n=7时,(7-1)/2+1=4,此时sqrt(10^4)=99.99, 239大于99.99
单n=11时,(11-1)/2+1=6,此时sqrt(10^6)=999.99, 21649大于1千
...
不知以后的数是不是成立,若是成立这是一个限制条件
单n=509时,(509-1)/2+1=255,x值大于sqrt(10^255)=3.16227766016837933199889354443270*10^127,这是涵盖其它类型的分解,这不是我想要的,x值应该直接大于10^254
看了n=17,n=71,n=211以后我又有点泄气了,好像以后没有再也没有x值254位,y值255位这种类型出现了,找不到它的限制条件了
ai给的分解建议:
椭圆曲线对我来说要求太高...

数论爱好者

经过一个多月的分析,观察,对R(509)的分解方法有进一步的缩小范围.
R(509)的因子必须具有1018k+1的形式.
因子的倒数的循环节长度为509,长度值是一个固定的素数值.
k不等于3a,虽说1018*3a+1产生素数,但是产生的素数的倒数的循环节长度值是合数,且大部分循环节值被3整除,不能被3整除的循环节长度都是偶数.
1018*(3a+2)+1不产生素数,永远被3整除.
k值只能是3a+1,且3a+1的末尾数数字不能含有3和8,若含有3和8,则1018*(3a+1)+1必被5整除.
进一步1018*(3a+1)+1必须是素数.
100个k值里面计算28个.
计算量为总k值的28%,72%的k值不需要计算.
猜测因子值大于3.1622776601683793319988935444327185337195551393252168268575048530*10^127,
即k值大于3.1063631239375042554016635996392127050290325533646530715692582050*10^124,这个计算量仍然不可接受,无法有大的进展.

数论爱好者

写了个随机数,然后用这个随机数验证1018*k+1是不是素数,如果是,进一步验证是不是R(509)的因子,希望碰碰运气.找到因子的概率是10^(-120),太低.
每次运行1000个素数验证的时间是200秒.

1. restart;
   
2. with(RandomTools):
   
3. with(numtheory):
   
4. with(FileTools):
   
5. 
   
6. # ===== 全局配置 =====
   
7. # R(509) 定义
   
8. R509 := (10^509 - 1)/9:
   
9. 
   
10. # 精度设置
    
11. Digits := 600;
    
12. 
    
13. # 计算关键边界值函数
    
14. calcBoundary := proc(root)
    
15.     local value;
    
16.     value := evalf(R509^(1/root));
    
17.     # 精确到小数点后1位并向上取整
    
18.     return ceil(value * 10) / 10;
    
19. end proc:
    
20. 
    
21. # 预先计算边界值
    
22. lower_small := calcBoundary(4);   # R509^(1/4)
    
23. upper_small := calcBoundary(3);   # R509^(1/3)
    
24. lower_large := upper_small;       # R509^(1/3)
    
25. upper_large := calcBoundary(2);   # R509^(1/2)
    
26. 
    
27. printf("小段数区间: %.1e 到 %.1e\n", lower_small, upper_small);
    
28. printf("大段数区间: %.1e 到 %.1e\n", lower_large, upper_large);
    
29. 
    
30. # 保存边界值到文件
    
31. save lower_small, upper_small, lower_large, upper_large, "R509_boundaries.m";
    
32. 
    
33. # ===== 搜索函数 =====
    
34. searchFactors := proc(lower_bound, upper_bound, target_primes)
    
35.     local primes_found, k, p, attempts, k_lower, k_upper, start_time;
    
36.     primes_found := [];
    
37.     attempts := 0;
    
38.     start_time := time();
    
39.    
    
40.     # 计算k的范围
    
41.     k_lower := ceil((lower_bound-1)/1018);
    
42.     k_upper := floor((upper_bound-1)/1018);
    
43.    
    
44.     printf("搜索范围: k = %a 到 %a (约%.3e个可能值)\n",
    
45.            k_lower, k_upper, k_upper - k_lower + 1);
    
46.    
    
47.     # 生成候选k值直到找到目标素数数量
    
48.     while nops(primes_found) < target_primes and attempts < 10^7 do
    
49.         # 在范围内生成随机k值
    
50.         k := Generate(integer(range = k_lower..k_upper));
    
51.         
    
52.         # 添加约束条件
    
53.         # 约束1: k必须是3a+1形式
    
54.         if k mod 3 <> 1 then
    
55.             attempts := attempts + 1;
    
56.             next;
    
57.         end if;
    
58.         
    
59.         # 约束2: k的末位数字不能是3或8
    
60.         if (k mod 10 = 3) or (k mod 10 = 8) then
    
61.             attempts := attempts + 1;
    
62.             next;
    
63.         end if;
    
64.         
    
65.         # 约束3: a不能是7k+5形式 (a = (k-1)/3)
    
66.         if ((k-1)/3) mod 7 = 5 then
    
67.             attempts := attempts + 1;
    
68.             next;
    
69.         end if;
    
70.         
    
71.         # 计算候选因子 p = 1018*k + 1
    
72.         p := 1018*k + 1;
    
73.         
    
74.         # 检查p是否为素数
    
75.         if isprime(p) then
    
76.             # 添加到素数列表
    
77.             primes_found := [op(primes_found), p];
    
78.             printf("发现候选素数: %.3e (k=%a)\n", p, k);
    
79.         end if;
    
80.         
    
81.         attempts := attempts + 1;
    
82.         
    
83.         # 每10000次尝试显示进度
    
84.         if attempts mod 10000 = 0 then
    
85.             printf("尝试次数: %a, 找到素数: %d/%d\n",
    
86.                    attempts, nops(primes_found), target_primes);
    
87.         end if;
    
88.     end do;
    
89.    
    
90.     printf("完成! 尝试次数: %a, 耗时: %.1f 秒\n",
    
91.            attempts, time() - start_time);
    
92.     return primes_found;
    
93. end proc:
    
94. 
    
95. # ===== 每日任务函数 =====
    
96. dailySearch := proc()
    
97.     local large_primes, small_primes, all_candidates, factor, i, found, q;
    
98.     global day_count;
    
99.     local start_time, total_time;
    
100.    
     
101.     start_time := time();
     
102.    
     
103.     # 初始化day_count
     
104.     if not assigned(day_count) then
     
105.         day_count := 0;
     
106.     end if;
     
107.    
     
108.     day_count := day_count + 1;
     
109.     printf("\n===== 第 %d 天搜索开始 =====\n", day_count);
     
110.    
     
111.     # 大段数区间搜索 (500个素数)
     
112.     printf("\n-- 大段数区间搜索 (目标500个素数) --\n");
     
113.     large_primes := searchFactors(lower_large, upper_large, 500);
     
114.     printf("在大段数区间找到 %d 个候选素数\n", nops(large_primes));
     
115.    
     
116.     # 小段数区间搜索 (500个素数)
     
117.     printf("\n-- 小段数区间搜索 (目标500个素数) --\n");
     
118.     small_primes := searchFactors(lower_small, upper_small, 500);
     
119.     printf("在小段数区间找到 %d 个候选素数\n", nops(small_primes));
     
120.    
     
121.     # 合并所有候选素数
     
122.     all_candidates := [op(large_primes), op(small_primes)];
     
123.     printf("\n总计候选素数: %d 个\n", nops(all_candidates));
     
124.    
     
125.     # 验证候选素数是否能整除R(509)
     
126.     found := false;
     
127.     printf("开始验证 %d 个候选因子...\n", nops(all_candidates));
     
128.     for i from 1 to nops(all_candidates) do
     
129.         factor := all_candidates[i];
     
130.         
     
131.         # 使用模幂运算验证整除性
     
132.         if Power(10, 509) mod (9*factor) = 1 then
     
133.             printf("成功! 发现因子: %a\n", factor);
     
134.             # 计算并输出另一个因子
     
135.             q := R509 / factor;
     
136.             printf("对应因子: %a\n", q);
     
137.             
     
138.             # 保存结果到文件
     
139.             save factor, q, "R509_factor_found.m";
     
140.             found := true;
     
141.             # 发现因子后可以继续或停止
     
142.         end if;
     
143.     end do;
     
144.    
     
145.     if not found then
     
146.         printf("今日未发现有效因子\n");
     
147.     end if;
     
148.    
     
149.     # 保存进度
     
150.     save day_count, "R509_progress.m";
     
151.    
     
152.     total_time := time() - start_time;
     
153.     printf("\n===== 第 %d 天搜索完成, 总耗时: %.1f 秒 =====\n", day_count, total_time);
     
154. end proc:
     
155. 
     
156. # ===== 加载进度 =====
     
157. # 尝试加载之前的进度
     
158. if FileTools:-Exists("R509_progress.m") then
     
159.     read "R509_progress.m";
     
160.     printf("检测到先前进度: 已执行 %d 天\n", day_count);
     
161. end if;
     
162. 
     
163. # ===== 执行每日搜索 =====
     
164. dailySearch();
     
165. 
     
166. # ===== 长期运行提示 =====
     
167. printf("\n提示: 每天运行此脚本一次，持续一年。");
     
168. printf("要明天继续搜索，请重新运行此脚本。\n");

复制代码