Commits

David Wilhelm committed 9e25ae4

p44: add brute force fake solution

  • Participants
  • Parent commits 3b0f4d7

Comments (0)

Files changed (1)

+#!/usr/bin/env python
+# -*- coding: UTF-8 -*-
+
+"""
+Pentagonal numbers are generated by the formula, P_(n)=n(3n−1)/2. The
+first ten pentagonal numbers are:
+
+1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...
+
+It can be seen that P_(4) + P_(7) = 22 + 70 = 92 = P_(8). However,
+their difference, 70 − 22 = 48, is not pentagonal.
+
+Find the pair of pentagonal numbers, P_(j) and P_(k), for which their
+sum and difference is pentagonal and D = |P_(k) − P_(j)| is minimised;
+what is the value of D?
+"""
+
+
+def p(n):
+    return n * (3*n - 1) / 2
+
+
+def genpentto(pent, n):
+    while pent[-1] < n:
+        pent.append(p(len(pent)))
+
+
+def printinfo(pent, k, j):
+    print 'P(%d) = %d, P(%d) = %d, sum = %d %s, diff = %d %s' % (
+        k, pent[k], j, pent[j],
+        pent[k] + pent[j], pent[k] + pent[j] in pent,
+        pent[k] - pent[j], pent[k] - pent[j] in pent,)
+
+
+def main():
+    """Notes:
+
+    Since the sequence of pentagonals is increasing, as soon as the
+    difference between terms is greater than D, the existing min
+    difference is guarnateed to be the minimum for the whole sequence.
+    """
+    diff = []
+    pent = [0, 1, 5]
+    done = False
+    k = 2
+    while not done:
+        if k >= len(pent):
+            genpentto(pent, p(k))
+        for j in xrange(1, k):
+            if pent[k] - pent[j] in pent:
+                while pent[-1] < pent[k] + pent[j]:
+                    genpentto(pent, pent[k] + pent[j])
+                if pent[k] + pent[j] in pent:
+                    diff.append(pent[k] - pent[j])
+                    printinfo(pent, k, j)
+                    # TODO: Fix the logic to test if D is really minimized.
+                    done = True
+        k += 1
+        print k, len(pent), pent[-1], pent[-1] - pent[-2]
+
+
+if __name__ == '__main__':
+    main()