K-Smith numbers

mathe

$\sum_{p<n}1/p=O(log(log(n)))$

liangbch

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))$了?

mathe

我们知道对于一个整数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))$

无心人

小心这么晚睡觉
将来要长皱纹的

无心人

我想
把范围设为10^8吧

无心人

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 编辑 ]

无心人

根据目前计算10^8的时间看
计算 10^12将花费的时间单位是天
即使用C语言写程序
似乎10 ^8花费时间将超过1小时
记录开始时间11:13

liangbch

报个到先，看看我是否时间尝试一下。

无心人

100000000的尝试失败了
竟然4个小时没出结果

无心人

上面的代码在查找上是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)