挑战R509分解

数论爱好者 发表于 2025-5-4 13:08:32

有一个网站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给的分解建议:
椭圆曲线对我来说要求太高...

数论爱好者 发表于 4 天前

经过一个多月的分析,观察,对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,这个计算量仍然不可接受,无法有大的进展.

数论爱好者 发表于 2 小时前

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

# ===== 全局配置 =====
# R(509) 定义
R509 := (10^509 - 1)/9:

# 精度设置
Digits := 600;

# 计算关键边界值函数
calcBoundary := proc(root)
local value;
value := evalf(R509^(1/root));
# 精确到小数点后1位并向上取整
return ceil(value * 10) / 10;
end proc:

# 预先计算边界值
lower_small := calcBoundary(4); # R509^(1/4)
upper_small := calcBoundary(3); # R509^(1/3)
lower_large := upper_small;    # R509^(1/3)
upper_large := calcBoundary(2); # R509^(1/2)

printf("小段数区间: %.1e 到 %.1e\n", lower_small, upper_small);
printf("大段数区间: %.1e 到 %.1e\n", lower_large, upper_large);

# 保存边界值到文件
save lower_small, upper_small, lower_large, upper_large, "R509_boundaries.m";

# ===== 搜索函数 =====
searchFactors := proc(lower_bound, upper_bound, target_primes)
local primes_found, k, p, attempts, k_lower, k_upper, start_time;
primes_found := [];
attempts := 0;
start_time := time();

# 计算k的范围
k_lower := ceil((lower_bound-1)/1018);
k_upper := floor((upper_bound-1)/1018);

printf("搜索范围: k = %a 到 %a (约%.3e个可能值)\n",
      k_lower, k_upper, k_upper - k_lower + 1);

# 生成候选k值直到找到目标素数数量
while nops(primes_found) < target_primes and attempts < 10^7 do
   # 在范围内生成随机k值
   k := Generate(integer(range = k_lower..k_upper));

   # 添加约束条件
   # 约束1: k必须是3a+1形式
   if k mod 3 <> 1 then
         attempts := attempts + 1;
         next;
   end if;

   # 约束2: k的末位数字不能是3或8
   if (k mod 10 = 3) or (k mod 10 = 8) then
         attempts := attempts + 1;
         next;
   end if;

   # 约束3: a不能是7k+5形式 (a = (k-1)/3)
   if ((k-1)/3) mod 7 = 5 then
         attempts := attempts + 1;
         next;
   end if;

   # 计算候选因子 p = 1018*k + 1
   p := 1018*k + 1;

   # 检查p是否为素数
   if isprime(p) then
         # 添加到素数列表
         primes_found := ;
         printf("发现候选素数: %.3e (k=%a)\n", p, k);
   end if;

   attempts := attempts + 1;

   # 每10000次尝试显示进度
   if attempts mod 10000 = 0 then
         printf("尝试次数: %a, 找到素数: %d/%d\n",
               attempts, nops(primes_found), target_primes);
   end if;
end do;

printf("完成! 尝试次数: %a, 耗时: %.1f 秒\n",
      attempts, time() - start_time);
return primes_found;
end proc:

# ===== 每日任务函数 =====
dailySearch := proc()
local large_primes, small_primes, all_candidates, factor, i, found, q;
global day_count;
local start_time, total_time;

start_time := time();

# 初始化day_count
if not assigned(day_count) then
   day_count := 0;
end if;

day_count := day_count + 1;
printf("\n===== 第 %d 天搜索开始 =====\n", day_count);

# 大段数区间搜索 (500个素数)
printf("\n-- 大段数区间搜索 (目标500个素数) --\n");
large_primes := searchFactors(lower_large, upper_large, 500);
printf("在大段数区间找到 %d 个候选素数\n", nops(large_primes));

# 小段数区间搜索 (500个素数)
printf("\n-- 小段数区间搜索 (目标500个素数) --\n");
small_primes := searchFactors(lower_small, upper_small, 500);
printf("在小段数区间找到 %d 个候选素数\n", nops(small_primes));

# 合并所有候选素数
all_candidates := ;
printf("\n总计候选素数: %d 个\n", nops(all_candidates));

# 验证候选素数是否能整除R(509)
found := false;
printf("开始验证 %d 个候选因子...\n", nops(all_candidates));
for i from 1 to nops(all_candidates) do
   factor := all_candidates;

   # 使用模幂运算验证整除性
   if Power(10, 509) mod (9*factor) = 1 then
         printf("成功! 发现因子: %a\n", factor);
         # 计算并输出另一个因子
         q := R509 / factor;
         printf("对应因子: %a\n", q);

         # 保存结果到文件
         save factor, q, "R509_factor_found.m";
         found := true;
         # 发现因子后可以继续或停止
   end if;
end do;

if not found then
   printf("今日未发现有效因子\n");
end if;

# 保存进度
save day_count, "R509_progress.m";

total_time := time() - start_time;
printf("\n===== 第 %d 天搜索完成, 总耗时: %.1f 秒 =====\n", day_count, total_time);
end proc:

# ===== 加载进度 =====
# 尝试加载之前的进度
if FileTools:-Exists("R509_progress.m") then
read "R509_progress.m";
printf("检测到先前进度: 已执行 %d 天\n", day_count);
end if;

# ===== 执行每日搜索 =====
dailySearch();

# ===== 长期运行提示 =====
printf("\n提示: 每天运行此脚本一次，持续一年。");
printf("要明天继续搜索，请重新运行此脚本。\n");

页: [1]

数学研发论坛's Archiver

挑战R509分解