数学研发论坛

 找回密码
 欢迎注册
楼主: medie2005

[讨论] K-Smith numbers

[复制链接]
发表于 2008-11-21 18:22:14 | 显示全部楼层
$\sum_{p<n}1/p=O(log(log(n)))$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-21 20:22:05 | 显示全部楼层
n以内整数中,平均每个数的素因子的个数计算方法(重复的值计算一次),应该如mathe所言。

更明确的描述应该是这样的。 如n以内素数的个数为m,将第i个素数记为$P_i$ 则n以内的数总的素因子的个数为:
$n/P_1 + n/P_2+n/P_3 + ..n/P_m$
故平均每个数素因子的个数为 $1/P_1+1/P_2+...+1/P_m$
我们知道,当n很大是,n以内的自然数的倒数有极限,$\sum_{i=1}^{n}1/i=log(n)+C,c=0.5722$,但不知道mathe如何推出n以内的素数的倒数和公式。

那么筛法求素数的复杂度 就是 $n*log(log(n))$了?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-21 21:58:34 | 显示全部楼层
我们知道对于一个整数x,它为素数的概率大概为$1/{log(x)}$,所以我们可以将
$sum_{p<n}1/p$近似写成$int_a^n1/{xlog(x)}dx=int_a^n{dlog(x)}/{log(x)}=int_{log(a)}^{log(n)}{dt}/t=O(log(log(n))$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-21 22:03:57 | 显示全部楼层
小心这么晚睡觉
将来要长皱纹的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-25 09:59:13 | 显示全部楼层
我想
把范围设为10^8吧
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-25 10:33:14 | 显示全部楼层
import Factoring
  import Primes

  readInt :: IO Integer
  readInt = readLn
  
  digitsSum n = if (n == 0) then 0 else ((n \`mod\` 10) + digitsSum (n \`div\` 10))
  addFactors (a, b) = toInteger (b) * (digitsSum a)
  isIn a l = any (==a) l
  
  smithNumber n = [ n' | n' <- [6..n], not (isPrime n'), let nFactors = primePowerFactorsL n', (digitsSum n') == sum (map (addFactors) nFactors)]
  smithNumber3 n = [n' | let smith = smithNumber n, n' <- smith, (isIn (n'+1) smith) && (isIn (n'+2) smith)]
  smithNumber4 n = [n' | let smith = smithNumber n, n' <- smith, (isIn (n'+1) smith) && (isIn (n'+2) smith) && (isIn (n'+3) smith)]
  
  main = do
           putStrLn "Input Max n:"
           n <- readInt
           let filename = "ksmith" ++ show(n) ++ ".TXT"
           writeFile filename (show \$ smithNumber3 n)
=========================================================
1000000内
[73615,209065,225951,283745,305455,342879,656743,683670,729066,747948,774858,879221,954590]
可以看到,不存在4以上的

[ 本帖最后由 无心人 于 2008-11-25 11:12 编辑 ]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-25 11:27:19 | 显示全部楼层
根据目前计算10^8的时间看
计算 10^12将花费的时间单位是天
即使用C语言写程序
似乎10 ^8花费时间将超过1小时
记录开始时间11:13
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-25 13:49:01 | 显示全部楼层
报个到先,看看我是否时间尝试一下。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-25 15:48:40 | 显示全部楼层
100000000的尝试失败了
竟然4个小时没出结果
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-25 16:13:01 | 显示全部楼层
上面的代码在查找上是O(n^2)
经人指点优化下

  import Factoring
  import Primes

  readInt :: IO Integer
  readInt = readLn
  
  digitsSum n = if (n == 0) then 0 else ((n  \`mod\` 10) + digitsSum (n \`div\` 10))
  addFactors (a, b) = toInteger (b) * (digitsSum a)
  f (a, b, c) = (b == a+1) && (c == b+1)
  
  smithNumber n = [ n' | n' <- [6..n], not (isPrime n'), let nFactors = primePowerFactorsL n', (digitsSum n') == sum (map (addFactors) nFactors)]
  filter3 ls = filter f (zip3 ls (tail ls) (drop 2 ls))
  smithNumber3 n = filter3 (smithNumber n)
  
  main = do
           putStrLn "Input Max n:"
           n <- readInt
           let filename = "ksmith" ++ show(n) ++ ".TXT"
           writeFile filename (show \$ smithNumber3 n)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2021-2-25 03:48 , Processed in 0.133241 second(s), 15 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表