home
>
Project Euler
>
ForNext
Shut the fuck up and write some code
Problem 21
10000未満の友愛数の和を求めよ
d(n) を n の真の約数の和と定義する. (真の約数とは n 以外の約数のことである. )
もし, d(a) = b かつ d(b) = a (a ≠ b のとき) を満たすとき, a と b は友愛数(親和数)であるという.
例えば, 220 の約数は 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 なので d(220) = 284 である.
また, 284 の約数は 1, 2, 4, 71, 142 なので d(284) = 220 である.
それでは10000未満の友愛数の和を求めよ.
Amicable numbers
Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers.
For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.
Evaluate the sum of all the amicable numbers under 10000.
考え方
自然数 n が、
( は素数、
は 0 以上の整数)
と素因数分解されるとき、n の約数の個数と 約数の総和は、次の公式で与えられる。
約数の個数：
約数の総和：
たとえば、 は、
と素因数分解され、約数は、
で、約数の個数 は、 個、
約数の総和は
である。
VBScript
JScript
Perl
PHP
Python
Ruby
PowerShell
Scala
更新日 : 2013.02.04
scala> def get_prime_factor(map:collection.mutable.Map[Long, Long], n: Long, factor: Long = 2) {
| if (n >= factor) {
| if (n % factor != 0 )
| get_prime_factor(map, n, factor + 1)
| else {
| if (map.contains(factor))
| map(factor) += 1
| else
| map += factor -> 1
|
| get_prime_factor(map, n / factor, factor)
| }
| }
| }
get_prime_factor: (map: scala.collection.mutable.Map[Long,Long], n: Long, factor: Long)Unit
scala> val map = collection.mutable.Map[Long, Long] ()
map: scala.collection.mutable.Map[Long,Long] = Map()
scala> get_prime_factor(map, 28)
scala> map
res1: scala.collection.mutable.Map[Long,Long] = Map(7 -> 1, 2 -> 2)
scala> map.transform((k,v) => (math.pow(k, v + 1) - 1).toLong / (k - 1)) res2: map.type = Map(7 -> 8, 2 -> 7) scala> map.values res3: Iterable[Long] = HashMap(8, 7) scala> map.values.reduceLeft(_*_) res4: Long = 56
scala> def sum_of_proper_divisors(n:Long):Long = {
| var map = collection.mutable.Map[Long, Long] ()
| get_prime_factor(map, n)
| if (map.size == 0) 0
| else {
| map.transform((k,v) => (math.pow(k, v + 1) - 1).toLong / (k - 1))
| map.values.reduceLeft(_*_) - n
| }
| }
sum_of_proper_divisors: (n: Long)Long
scala> sum_of_proper_divisors(220) res5: Long = 284 scala> sum_of_proper_divisors(284) res6: Long = 220
scala> var ami_list:List[Long] = List()
ami_list: List[Long] = List()
scala> for (i <- 1 to 10000) {
| val n = sum_of_proper_divisors(i)
| if (i != n) {
| val m = sum_of_proper_divisors(n)
| if (i == m) ami_list = n::ami_list
| }
| }
scala> ami_list
res8: List[Long] = List(6232, 6368, 5020, 5564, 2620, 2924, 1184, 1210, 220, 284)
scala> ami_list.sum
res9: Long = 31626
F#
更新日 : 2013.02.04
> let mutable map:Map<int, int> = Map.empty;; val mutable map : Map<int,int> = map [] > let rec get_prime_factor (map:Map<int, int> byref) (n:int) (factor: int) = - if n >= factor then - if n % factor <> 0 then - get_prime_factor &map n (factor + 1) - else - if Map.containsKey factor map then - let n = map.[factor] + 1 - map <- map.Remove factor - map <- (map |> Map.add factor n) - else - map <- (map |> Map.add factor 1) - - get_prime_factor &map (n / factor) factor - ;; val get_prime_factor : byref<Map<int,int>> -> int -> int -> unit > get_prime_factor &map 28 2;; val it : unit = () > map - ;; val it : Map<int,int> = map [(2, 2); (7, 1)]
> map - |> Map.iter (fun k t -> printf "%d -> %d\n" k t) - ;; 2 -> 2 7 -> 1 val it : unit = ()
> map - |> Map.map (fun k t -> System.Math.Pow(float k,float t)) - ;; val it : Map<int,float> = map [(2, 4.0); (7, 7.0)]
> map - |> Map.map (fun k t -> System.Math.Pow(float k,(float t) + 1.0)) - ;; val it : Map<int,float> = map [(2, 8.0); (7, 49.0)]
> map - |> Map.map (fun k t -> System.Math.Pow(float k,(float t) + 1.0) - 1.0) - ;; val it : Map<int,float> = map [(2, 7.0); (7, 48.0)]
> map - |> Map.map (fun k t -> (System.Math.Pow(float k,(float t) + 1.0) - 1.0) / float (k - 1)) - ;; val it : Map<int,float> = map [(2, 7.0); (7, 8.0)]
> map - |> Map.map (fun k t -> (System.Math.Pow(float k,(float t) + 1.0) - 1.0) / float (k - 1)) - |> Map.toList - ;; val it : (int * float) list = [(2, 7.0); (7, 8.0)]
> map - |> Map.map (fun k t -> (System.Math.Pow(float k,(float t) + 1.0) - 1.0) / float (k - 1)) - |> Map.toList - |> List.map (fun (k, t) -> t) - ;; val it : float list = [7.0; 8.0]
> map - |> Map.map (fun k t -> (System.Math.Pow(float k,(float t) + 1.0) - 1.0) / float (k - 1)) - |> Map.toList - |> List.map (fun (k, t) -> t) - |> List.reduce(*) - ;; val it : float = 56.0
> int (map - |> Map.map (fun k t -> (System.Math.Pow(float k,(float t) + 1.0) - 1.0) / float (k - 1)) - |> Map.toList - |> List.map (fun (k, t) -> t) - |> List.reduce(*)) - ;; val it : int = 56
> let sum_of_proper_divisors (n:int):int = - let mutable map:Map<int, int> = Map.empty - get_prime_factor &map n 2 - - if map.IsEmpty then 0 - else - int (map - |> Map.map (fun k t -> (System.Math.Pow(float k,(float t) + 1.0) - 1.0) / float (k - 1)) - |> Map.toList - |> List.map (fun (k, t) -> t) - |> List.reduce(*)) - n - ;; val sum_of_proper_divisors : int -> int
> sum_of_proper_divisors 220;; val it : int = 284 > sum_of_proper_divisors 284;; val it : int = 220
> - let mutable ami_list:List<int> = [];; val mutable ami_list : List<int> = [] > for i in [1 .. 10000] do - let n = sum_of_proper_divisors i - if i <> n then - let m = sum_of_proper_divisors n - if i = m then ami_list <- n::ami_list - ;; val it : unit = ()
> ami_list - ;; val it : List<int> = [6232; 6368; 5020; 5564; 2620; 2924; 1184; 1210; 220; 284]
> ami_list - |> List.reduce(+) - ;; val it : int = 31626
