Pollock octahedral numbers conjecture.

[krucifi]

In additive number theory, the Pollock octahedral numbers conjecture is an unproven conjecture that every positive integer is the sum of at most seven octahedral numbers.

Ripped this from wikipedia. wondering if anyone here would be able to prove or disprove it.

link http://en.wikipedia.org/wiki/Pollock_oc ... conjecture

[gmalivuk]

Ripped this from wikipedia. wondering if anyone here would be able to prove or disprove it.

It's been unproven for 162 years. I'm going to go out on a limb here and guess that no one's going to prove or disprove it in a forum thread.

[PM 2Ring]

It's been unproven for 162 years. I'm going to go out on a limb here and guess that no one's going to prove or disprove it in a forum thread.

FWIW, here's a simple Python program that attempts to express integers as the sum of at most seven octahedral numbers using a simple greedy algorithm, and prints those integers which it fails on. As a bonus, it has an inverse of the octahedral number function.

Code: Select all

#! /usr/bin/env python

'''
 Investigating the Pollock octahedral numbers conjecture:
 every positive integer is the sum of at most seven octahedral numbers.
 Find numbers that can't be expressed as such a sum by the greedy algorithm.

 See http://en.wikipedia.org/wiki/Pollock_octahedral_numbers_conjecture
 
'''

import sys, math
from bisect import bisect

#Calculate the nth octahedral number
def octa(n): return n * (2*n*n + 1) / 3

#Invert octa() using u**3 + v**3 = (u+v)**3 - 3*u*v*(u+v)
def invocta(y):
    d = math.sqrt(729 * y * y + 6)
    w = (27 * y + d) / 36.
    u = math.pow(w, 1. / 3)
    x = u - 1. / (6 * u)
   
    #Perform one round of Newton's method to reduce error
    #x2 = x * x
    ##x += (3 * y -  x * (2 * x2 + 1)) / (6 * x2 + 1)
    #x = (3 * y + 4 * x * x2) / (6 * x2 + 1)
    return x

def pollock(m):
    octalist = [octa(i) for i in xrange(1, m + 1)]
    octamax = octalist[-1]
    print >>sys.stderr, 'Searching up to %d = octa(%d)' % (octamax, m)

    #Find highest j, octa(j): octa(j) < i, j<=hi
    def octaceil(i, hi=m):
        j = bisect(octalist, i, hi=hi)       
        return j, octalist[j-1]

    #See if we can produce i as a sum of octahedral numbers <= octa(hi)
    def greedy(i, hi):
        for k in xrange(7):
            j, v = octaceil(i, hi)
            hi = j
            i -= v
            if i == 0:
                return True
        return False

    #Find octahedral sets that sum to i
    count = 0
    for i in xrange(1, octamax + 1):
        if not greedy(i, m):
            count += 1
            print '%d,' % i,
        if (i + 1) % 50 == 0:
            print
    print
    print >>sys.stderr, '%d exceptions found. Ratio=%f' % (count, float(count) / octamax)

def main():
    m = len(sys.argv) > 1 and int(sys.argv[1]) or 5
    pollock(m)   

if __name__ == '__main__':
    main()


Here's some output:

Code: Select all

Searching up to 2255 = octa(15)
36,
61, 74, 79, 80,
102, 115, 120, 121, 128, 140, 145,
163, 176, 181, 182, 189,
201, 206, 207, 214, 219, 220, 224, 225, 226, 248,
261, 266, 267, 274, 286, 291, 292, 299,
304, 305, 309, 310, 311, 327, 332, 333, 340,
361, 374, 379, 380, 387, 399,
404, 405, 412, 417, 418, 422, 423, 424, 440, 445, 446,
453, 458, 459, 463, 464, 465, 471, 472, 478, 483, 484, 488,
506, 519, 524, 525, 532, 544, 549,
550, 557, 562, 563, 567, 568, 569, 585, 590, 591, 598,
603, 604, 608, 609, 610, 616, 617, 623, 628, 629, 633, 634, 646,
651, 652, 659, 664, 665, 669, 687,
700, 705, 706, 713, 725, 730, 731, 738, 743, 744, 748, 749,
750, 766, 771, 772, 779, 784, 785, 789, 790, 791, 797, 798,
804, 809, 810, 814, 815, 827, 832, 833, 840, 845, 846,
850, 851, 852, 858, 859, 865, 870, 871, 875, 876, 877, 883, 884, 888, 889, 890,
908, 921, 926, 927, 934, 946,
951, 952, 959, 964, 965, 969, 970, 971, 987, 992, 993,
1000, 1005, 1006, 1010, 1011, 1012, 1018, 1019, 1025, 1030, 1031, 1035, 1036, 1048,
1053, 1054, 1061, 1066, 1067, 1071, 1072, 1073, 1079, 1080, 1086, 1091, 1092, 1096, 1097, 1098,
1104, 1105, 1109, 1110, 1111, 1114, 1115, 1116, 1117, 1133, 1138, 1139, 1146,
1151, 1152, 1173, 1186, 1191, 1192, 1199,
1211, 1216, 1217, 1224, 1229, 1230, 1234, 1235, 1236,
1252, 1257, 1258, 1265, 1270, 1271, 1275, 1276, 1277, 1283, 1284, 1290, 1295, 1296,
1300, 1301, 1313, 1318, 1319, 1326, 1331, 1332, 1336, 1337, 1338, 1344, 1345,
1351, 1356, 1357, 1361, 1362, 1363, 1369, 1370, 1374, 1375, 1376, 1379, 1380, 1381, 1382, 1398,
1403, 1404, 1411, 1416, 1417, 1421, 1422, 1423, 1429, 1430, 1436, 1441, 1442, 1446, 1447, 1448,
1454, 1455, 1459, 1460, 1461, 1464, 1465, 1466, 1467, 1486, 1499,
1504, 1505, 1512, 1524, 1529, 1530, 1537, 1542, 1543, 1547, 1548, 1549,
1565, 1570, 1571, 1578, 1583, 1584, 1588, 1589, 1590, 1596, 1597,
1603, 1608, 1609, 1613, 1614, 1626, 1631, 1632, 1639, 1644, 1645, 1649,
1650, 1651, 1657, 1658, 1664, 1669, 1670, 1674, 1675, 1676, 1682, 1683, 1687, 1688, 1689, 1692, 1693, 1694, 1695,
1711, 1716, 1717, 1724, 1729, 1730, 1734, 1735, 1736, 1742, 1743, 1749,
1754, 1755, 1759, 1760, 1761, 1767, 1768, 1772, 1773, 1774, 1777, 1778, 1779, 1780, 1790, 1795, 1796,
1800, 1801, 1802, 1808, 1809, 1824, 1829, 1830,
1851, 1864, 1869, 1870, 1877, 1889, 1894, 1895,
1902, 1907, 1908, 1912, 1913, 1914, 1930, 1935, 1936, 1943, 1948, 1949,
1953, 1954, 1955, 1961, 1962, 1968, 1973, 1974, 1978, 1979, 1991, 1996, 1997,
2004, 2009, 2010, 2014, 2015, 2016, 2022, 2023, 2029, 2034, 2035, 2039, 2040, 2041, 2047, 2048,
2052, 2053, 2054, 2057, 2058, 2059, 2060, 2076, 2081, 2082, 2089, 2094, 2095, 2099,
2100, 2101, 2107, 2108, 2114, 2119, 2120, 2124, 2125, 2126, 2132, 2133, 2137, 2138, 2139, 2142, 2143, 2144, 2145,
2155, 2160, 2161, 2165, 2166, 2167, 2173, 2174, 2189, 2194, 2195,
2202, 2207, 2208, 2212, 2213, 2214, 2220, 2221, 2227, 2232, 2233, 2237, 2238, 2239, 2245, 2246,
2250, 2251, 2252,
511 exceptions found. Ratio=0.226608


As we search higher integers the success ratio appears to decrease:

Code: Select all

Searching up to 670 = octa(10)
110 exceptions found. Ratio=0.164179
Searching up to 5340 = octa(20)
1424 exceptions found. Ratio=0.266667
Searching up to 18010 = octa(30)
5808 exceptions found. Ratio=0.322488
Searching up to 42680 = octa(40)
15320 exceptions found. Ratio=0.358950
Searching up to 83350 = octa(50)
32176 exceptions found. Ratio=0.386035
Searching up to 144020 = octa(60)
58637 exceptions found. Ratio=0.407145
Searching up to 228690 = octa(70)
97028 exceptions found. Ratio=0.424277
Searching up to 341360 = octa(80)
149849 exceptions found. Ratio=0.438976
Searching up to 486030 = octa(90)
219618 exceptions found. Ratio=0.451861
Searching up to 666700 = octa(100)
308779 exceptions found. Ratio=0.463145

Searching up to 1302125 = octa(125)
633237 exceptions found. Ratio=0.486310
Searching up to 2250050 = octa(150)
1134999 exceptions found. Ratio=0.504433
Searching up to 3572975 = octa(175)
1855935 exceptions found. Ratio=0.519437
Searching up to 5333400 = octa(200)
2837496 exceptions found. Ratio=0.532024


Edit: Arrrgh! I had a stupid sign error under the square root in the invocta() function.

[notzeb]

Ripped this from wikipedia. wondering if anyone here would be able to prove or disprove it.

It's been unproven for 162 years. I'm going to go out on a limb here and guess that no one's going to prove or disprove it in a forum thread.

Actually, this problem looks quite approachable. Using the circle method, you can show that every sufficiently large number is a sum of at most seven cubes, and octahedral numbers are more common than the cubes, and appear to have fewer congruence conditions placed on them. It's possible that the real reason it hasn't been solved yet is simply that no one has tried applying the circle method to it recently.

[rheyns]

I haven't yet learned enough about the circle method to tackle the problem theoretically but I have made empirical progress on a related problem.

For a while now I've been working on Pollock's (Tetrahedral) Conjecture and I think I've made some good progress. Previously published distribution statistics go up to 40B integers and now I've pushed that up to 400B. If you want to read more about it I have a blog post with links to the code at http://euler.rouxheyns.com (I apparently can't make links yet )

If you want to apply my technique to this problem to get some numerical insight you're welcome to use the code and I'll be happy to answer any questions you have.