Partition function P: Difference between revisions

← Older edit Newer edit →

Content deleted Content added

Inline

@@ Line 210: / Line 210: @@
 p(6666) = 193655306161707661080005073394486091998480950338405932486880600467114423441282418165863 (0.8s)
 </pre>
+=={{header|Python}}==
+This follows the algorithm from the Mathloger video closely
+<lang python>from itertools import islice
+def posd():
+    "diff between position numbers. 1, 2, 3... interleaved with  3, 5, 7..."
+    count, odd = 1, 3
+    while True:
+        yield count
+        yield odd
+        count, odd = count + 1, odd + 2
+def pos_gen():
+    "position numbers. 1 3 2 5 7 4 9 ..."
+    val = 1
+    diff = posd()
+    while True:
+        yield val
+        val += next(diff)
+def plus_minus():
+    "yield (list_offset, sign) or zero for Partition calc"
+    n, sign = 0, [1, 1]
+    p_gen = pos_gen()
+    out_on = next(p_gen)
+    while True:
+        n += 1
+        if n == out_on:
+            next_sign = sign.pop(0)
+            if not sign:
+                sign = [-next_sign] * 2
+            yield -n, next_sign
+            out_on = next(p_gen)
+        else:
+            yield 0
+def part(n):
+    "Partition numbers"
+    p = [1]
+    p_m = plus_minus()
+    mods = []
+    for _ in range(n):
+        next_plus_minus = next(p_m)
+        if next_plus_minus:
+            mods.append(next_plus_minus)
+        p.append(sum(p[offset] * sign for offset, sign in mods))
+    return p[-1]
+print("(Intermediaries):")
+print("    posd:", list(islice(posd(), 10)))
+print("    pos_gen:", list(islice(pos_gen(), 10)))
+print("    plus_minus:", list(islice(plus_minus(), 15)))
+print("\nPartitions:", [part(x) for x in range(15)])</lang>
+{{out}}
+<pre>(Intermediaries):
+    posd: [1, 3, 2, 5, 3, 7, 4, 9, 5, 11]
+    pos_gen: [1, 2, 5, 7, 12, 15, 22, 26, 35, 40]
+    plus_minus: [(-1, 1), (-2, 1), 0, 0, (-5, -1), 0, (-7, -1), 0, 0, 0, 0, (-12, 1), 0, 0, (-15, 1)]
+Partitions: [1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135]</pre>
+;Stretch goal:
+From command line after running the above
+<pre>(Intermediaries):
+    posd: [1, 3, 2, 5, 3, 7, 4, 9, 5, 11]
+    pos_gen: [1, 2, 5, 7, 12, 15, 22, 26, 35, 40]
+    plus_minus: [(-1, 1), (-2, 1), 0, 0, (-5, -1), 0, (-7, -1), 0, 0, 0, 0, (-12, 1), 0, 0, (-15, 1)]
+Partitions: [1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135]<<pre>
 =={{header|REXX}}==