ミルカさんの「約数の和」を Squeak Smalltalk で

結城さんの「数学ガール」より。ミルカさん人気にあからさまに便乗(^_^;)。

まず手始めにレシーバを素因数分解して結果を bag に入れて返す #primeFactorize を定義します。bag に入れているのは気分。ｗ

Integer >> primeFactorize
    | n primeFactors |
    n := self.
    primeFactors := Bag new.
    (Integer primesUpTo: self sqrt + 1) do: [:prime |
        | exp |
        exp := 0.
        [n isDivisibleBy: prime] whileTrue: [n := n / prime. exp := exp + 1].
        primeFactors add: prime withOccurrences: exp].
    n > 1 ifTrue: [primeFactors add: n].
    ^primeFactors

10 primeFactorize     "=> a Bag(2 5) "
1024 primeFactorize   "=> a Bag(2 2 2 2 2 2 2 2 2 2) "
108 primeFactorize    "=> a Bag(2 2 3 3 3) "
360 primeFactorize    "=> a Bag(2 2 2 3 3 5) "

次に、積（#product）も Collection>>#sum を倣って（でも少し手を加えて）定義しましょう。ちょっとめんどくさいことになっているのは、たとえば bag のような、順序付きでないコレクションでも使えるようにしているため。

Collection >> product
    | sample notYet |
    sample := self anyOne.
    notYet := true.
    ^self inject: sample into: [:accum :each |
        (notYet and: [each == sample])
            ifTrue: [notYet := false. accum]
            ifFalse: [accum * each]]

10 primeFactorize product     "=> 10 "
1024 primeFactorize product   "=> 1024 "
108 primeFactorize product    "=> 108 "
360 primeFactorize product    "=> 360 "

全約数を列挙する #allFactors も。

Integer >> allFactors
    | allFactors factors |
    allFactors := Set with: 1.
    factors := self primeFactorize asArray.
    (1 to: factors size) do: [:i |
        factors combinations: i atATimeDo: [:comb | allFactors add: comb product]].
    ^allFactors asSortedArray

10 allFactors     "=> #(1 2 5 10) "
1024 allFactors   "=> #(1 2 4 8 16 32 64 128 256 512 1024) "
108 allFactors    "=> #(1 2 3 4 6 9 12 18 27 36 54 108) "
360 allFactors    "=> #(1 2 3 4 5 6 8 9 10 12 15 18 20 24 30 36 40 45 60 72 90 120 180 360) "

これを #sum すると、とりあえずの答えが得られます。

10 allFactors sum     "=> 18 "
1024 allFactors sum   "=> 2047 "
108 allFactors sum    "=> 280 "
360 allFactors sum    "=> 1170 "

以上をふまえて、ミルカさんの解答に倣った #sumOfAllFactors 。

Integer >> sumOfAllFactors
    | factors |
    factors := self primeFactorize.
    ^factors asSet inject: 1 into: [:result :prime |
        | exp |
        exp := factors occurrencesOf: prime.
        result * (1 - (prime raisedTo: (exp + 1))) / (1 - prime)]

10 sumOfAllFactors     "=> 18 "
1024 sumOfAllFactors   "=> 2047 "
108 sumOfAllFactors    "=> 280 "
360 sumOfAllFactors    "=> 1170 "