[seqfan] Distinct Values of the Sum n Copies (iterated convolutions)

Ron Hardin rhhardin at att.net
Sun Apr 28 20:34:14 CEST 2013


Take a function, say x*y with x,y in 0..k .
Sum up n realizations of that.
Form the table T(n,k) of the number of possible distinct values for the sum.

In addition, the smallest unattained value for various n, and the apparent 
formula for large n columns.

Here's six functions grinding away on the laptop at the moment...

formulas, comments?

===

/tmp/dgu
T(n,k)=Number of distinct values of the sum of n products of two 0..k integers

Table starts
..2..4..7..10..15..19..26..31..37..43...54...60...73...81...90...98..115..124
..3..8.16..27..42..59..81.105.134.167..203..241..285..331..381..436..495..556
..4.12.25..43..67..95.130.169.215.267..324..385..454..527..606..692..784..880
..5.16.34..59..92.131.179.233.296.367..445..529..623..723..831..948.1073.1204
..6.20.43..75.117.167.228.297.377.467..566..673..792..919.1056.1204.1362.1528
..7.24.52..91.142.203.277.361.458.567..687..817..961.1115.1281.1460.1651.1852
..8.28.61.107.167.239.326.425.539.667..808..961.1130.1311.1506.1716.1940.2176
..9.32.70.123.192.275.375.489.620.767..929.1105.1299.1507.1731.1972.2229.2500
.10.36.79.139.217.311.424.553.701.867.1050.1249.1468.1703.1956.2228.2518.2824
.11.40.88.155.242.347.473.617.782.967.1171.1393.1637.1899.2181.2484.2807.3148

Row 1 is A027384

a(k) such that T(n,k) = n*k^2 - a(k) for large n
 -1 0 2 5 8 13 17 23 28 33 39 47 53 61 69 76 83 92 100 110 118

Minimum value unattainable as the sum of 2 attained values of a*b with a,b 0..n 
integers
 3 7 14 23 38 47 68 87 115 147 183 203 245 291 341 395 453 503 568

Minimum value unattainable as the sum of 3 attained values of a*b with a,b 0..n 
integers
 4 11 23 39 63 83 117 151 196 247 304 347 414 487 566 651 742 827
===

/tmp/dgv
T(n,k)=Number of distinct values of the sum of n products of three 0..k integers

Table starts
..2..5..11..17...31...41...66...81..101..121...174...195...267...302...344
..3.12..36..75..157..254..434..635..911.1237..1734..2162..2908..3611..4461
..4.20..63.141..284..478..780.1156.1667.2298..3111..4012..5213..6520..8063
..5.28..90.205..409..694.1123.1668.2396.3298..4442..5741..7410..9266.11443
..6.36.117.269..534..910.1466.2180.3125.4298..5773..7469..9607.12010.14818
..7.44.144.333..659.1126.1809.2692.3854.5298..7104..9197.11804.14754.18193
..8.52.171.397..784.1342.2152.3204.4583.6298..8435.10925.14001.17498.21568
..9.60.198.461..909.1558.2495.3716.5312.7298..9766.12653.16198.20242.24943
.10.68.225.525.1034.1774.2838.4228.6041.8298.11097.14381.18395.22986.28318
.11.76.252.589.1159.1990.3181.4740.6770.9298.12428.16109.20592.25730.31693

Row 1 is A027426

a(k) such that T(n,k) = n*k^3 - a(k) for large n
 -1 4 18 51 91 170 249 380 520 702 882 1171 1378 1710 2057 2447 2795

Minimum value unattainable as the sum of 2 attained values of a*b*c with a,b,c 
0..n integers
 3 7 23 23 71 71 289 311 311 311 479 479 1559 1559 1559 1559 4253

Minimum value unattainable as the sum of 3 attained values of a*b*c with a,b,c 
0..n integers
 4 15 50 110 222 379 632 977 1372 1911 2773 3325 4579 5647 6949 8837

Minimum value unattainable as the sum of 4 attained values of a*b*c with a,b,c 
0..n integers
 5 23 77 174 347 595 975 1489 2101 2911 4104 5053 6776 8391 10324 12933
===

/tmp/dgw
T(n,k)=Number of distinct values of the sum of a*b+a*c+b*c over n sets of three 
a,b,c 0..k integers

Table starts
..3...8..16..25..40...59...79..104..133..166..205..244..290..339..392..448..516
..6..20..44..78.123..178..244..322..411..510..622..743..876.1022.1178.1345.1525
..9..32..71.126.198..286..391..514..654..810..985.1175.1383.1610.1853.2113.2392
.12..44..98.174.273..394..538..706..897.1110.1348.1607.1890.2198.2528.2881.3259
.15..56.125.222.348..502..685..898.1140.1410.1711.2039.2397.2786.3203.3649.4126
.18..68.152.270.423..610..832.1090.1383.1710.2074.2471.2904.3374.3878.4417.4993
.21..80.179.318.498..718..979.1282.1626.2010.2437.2903.3411.3962.4553.5185.5860
.24..92.206.366.573..826.1126.1474.1869.2310.2800.3335.3918.4550.5228.5953.6727
.27.104.233.414.648..934.1273.1666.2112.2610.3163.3767.4425.5138.5903.6721.7594
.30.116.260.462.723.1042.1420.1858.2355.2910.3526.4199.4932.5726.6578.7489.8461

a(k) such that T(n,k) = 3*n*k^2 - a(k) for large n
 0 4 10 18 27 38 50 62 75 90 104 121 138 154 172 191 209 229 251

Minimum value unattainable as the sum of 1 attained values of a*b+a*c+b*c with 
a,b,c 0..n integers
 2 6 10 10 13 22 22 22 22 22 37 37 37 37 37 37 37 58 58 58 58

Minimum value unattainable as the sum of 2 attained values of a*b+a*c+b*c with 
a,b,c 0..n integers
 5 18 40 70 109 154 209 285 373 458 568 670 802 946 1102 1246 1424

Minimum value unattainable as the sum of 3 attained values of a*b+a*c+b*c with 
a,b,c 0..n integers
 8 30 67 118 184 262 356 477 616 758 931 1102 1309 1534 1777 2014
===

/tmp/dgz
T(n,k)=Number of distinct values of the sum of n products of a 0..k-1 and a 0..k 
integer

Table starts
.1..3..6...9..14..18..25..30..36..42...53...59...72...80...89...97..114..123
.1..5.12..22..36..53..74..98.126.158..193..231..274..320..369..423..481..542
.1..7.18..34..56..83.116.154.198.248..303..363..430..502..579..663..753..848
.1..9.24..46..76.113.158.210.270.338..413..495..586..684..789..903.1025.1154
.1.11.30..58..96.143.200.266.342.428..523..627..742..866..999.1143.1297.1460
.1.13.36..70.116.173.242.322.414.518..633..759..898.1048.1209.1383.1569.1766
.1.15.42..82.136.203.284.378.486.608..743..891.1054.1230.1419.1623.1841.2072
.1.17.48..94.156.233.326.434.558.698..853.1023.1210.1412.1629.1863.2113.2378
.1.19.54.106.176.263.368.490.630.788..963.1155.1366.1594.1839.2103.2385.2684
.1.21.60.118.196.293.410.546.702.878.1073.1287.1522.1776.2049.2343.2657.2990

Row 1 is A027424

a(k) such that T(n,k) = n*k*(k-1) - a(k) for large n
 -1 -1 0 2 4 7 10 14 18 22 27 33 38 44 51 57 63 70 77 85 92 100

Minimum value unattainable as the sum of 2 attained values of i*j with i in 
0..n-1 and j in 0..n
 1 5 11 19 33 47 68 87 115 147 175 203 245 291 329 382 439 500 565

Minimum value unattainable as the sum of 3 attained values of i*j with i in 
0..n-1 and j in 0..n
 1 7 17 31 53 77 110 143 187 237 285 335 401 473 539 622 711 806

Minimum value unattainable as the sum of 4 attained values of i*j with i in 
0..n-1 and j in 0..n
 1 9 23 43 73 107 152 199 259 327 395 467 557 655 749 862 983 1112
===

/tmp/dgy
T(n,k)=Number of distinct values of the sum of i*(i-1) over n realizations of i 
in 0..k

Table starts
.1..2..3..4..5...6...7...8...9..10..11..12..13..14..15...16...17...18...19...20
.1..3..6..9.14..19..25..32..39..47..56..64..76..87..99..109..123..138..152..167
.1..4..9.15.26..36..49..66..85.103.130.152.180.214.247..276..320..362..399..444
.1..5.12.21.36..51..71..94.123.150.188.223.263.310.359..409..465..523..586..653
.1..6.15.27.46..66..92.122.160.195.243.290.344.403.466..532..605..680..762..848
.1..7.18.33.56..81.113.150.196.240.298.356.423.495.571..653..744..835..936.1040
.1..8.21.39.66..96.134.178.232.285.353.422.501.586.676..773..881..989.1107.1232
.1..9.24.45.76.111.155.206.268.330.408.488.579.677.781..893.1017.1143.1278.1423
.1.10.27.51.86.126.176.234.304.375.463.554.657.768.886.1013.1153.1296.1449.1614
.1.11.30.57.96.141.197.262.340.420.518.620.735.859.991.1133.1289.1449.1620.1804

a(k) such that T(n,k) = n*k*(k-1)/2 - a(k) for large n
 -1 -1 0 3 4 9 13 18 20 30 32 40 45 51 59 67 71 81 90 96 107

Minimum even value unattainable as the sum of 3 attained values of i*(i-1) with 
i in 0..n
 2 8 16 22 48 58 58 94 136 136 190 198 274 282 346 346 490 562 628

Minimum even value unattainable as the sum of 4 attained values of i*(i-1) with 
i in 0..n
 2 10 22 34 68 88 118 150 208 250 338 390 436 570 598 698 806 868

Minimum even value unattainable as the sum of 5 attained values of i*(i-1) with 
i in 0..n
 2 12 28 46 88 118 160 206 304 340 448 522 592 752 878 964 1078 1252

Minimum even value unattainable as the sum of 6 attained values of i*(i-1) with 
i in 0..n
 2 14 34 58 108 148 202 262 376 430 558 654 784 934 1088 1228 1378
===

/tmp/dgx
T(n,k)=Number of distinct values of the sum of i^2 over n realizations of i in 
0..k

Table starts
..2..3..4...5...6...7...8...9..10..11...12...13...14...15...16...17...18...19
..3..6.10..15..20..27..34..42..51..61...71...83...94..106..120..135..148..165
..4.10.19..32..45..67..88.116.145.179..212..260..300..347..402..464..517..592
..5.14.29..50..74.111.149.197.247.308..370..451..526..613..706..815..914.1037
..6.18.38..66..99.147.201.262.332.411..498..601..702..819..946.1078.1221.1375
..7.22.47..82.124.183.250.326.414.513..621..749..874.1018.1176.1338.1515.1706
..8.26.56..98.149.219.299.390.496.614..742..894.1045.1215.1404.1597.1807.2032
..9.30.65.114.174.255.348.454.577.715..863.1038.1216.1412.1630.1856.2098.2357
.10.34.74.130.199.291.397.518.658.815..984.1182.1385.1608.1855.2114.2388.2681
.11.38.83.146.224.327.446.582.739.915.1105.1326.1554.1804.2080.2370.2677.3005

Row 1 is A000027(n+1)
Row 2 is A047800
Row 3 is A034966
Row 4 is A047801
Row 5 is A132432(n+1)
Row 6 is A132438(n+1)

Minimum value unattainable as the sum of 5 attained values of i^2 with i in 0..n
 6 15 33 55 78 119 177 231 286 348 369 519 622 695 818 943 1041 1188

Minimum value unattainable as the sum of 6 attained values of i^2 with i in 0..n
 7 19 42 71 103 155 226 295 367 448 554 672 791 904 1066 1199 1375

Minimum value unattainable as the sum of 7 attained values of i^2 with i in 0..n
 8 23 51 87 128 191 275 359 459 548 675 816 960 1100 1316 1455 1664


 rhhardin at mindspring.com
rhhardin at att.net (either)



More information about the SeqFan mailing list