Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

A well known theorem of Gauss says that any natural number $n$ may be written as the sum of three triangular numbers - $$ n={a_{1} \choose 2}+{a_{2} \choose 2}+{a_{3} \choose 2} $$

The following question came up over the course of my work - Does there exist a (slowly growing) function $\omega(n)$ which tends to infinity with $n$ such that any natural number $n$ may be written in the following form - $$ n=\sum_{i=1}^{k}{a_{i} \choose 2}\mbox{ subject to }\prod_{i=1}^{k}a_{i}\leq\frac{n}{\omega(n)} $$

If we choose the largest possible $a_{1}$, then the largest possible $a_{2}$ etc; we can guarantee $\prod_{i=1}^{k}a_{i}\leq Cn$ for some absolute constant $C$ (NOT QUITE - SEE BELOW). The question then is, can we do any better?

[EDIT 1: In my rush to post this, I did not check my calculations very well - if you actually do what is described, you only get $\prod_{i=1}^{k}a_{i} \leq 2^{\log_2\log_2 n}n^{1/2+1/4...} = O(n\log n)$ (as Erick Wong and Emil Jeřábek pointed out). The question of how small you can make $\prod_{i=1}^{k}a_i$ still remains.]

[EDIT 2: Will Jagy has computed what the best possible product for $n\leq10^7$ and based off this data, the existence of an $\omega$ as asked above seems unlikely. That for some infinite family of natural numbers $n$, the product must be $\Theta(n)$ is a plausible conjecture - though how one might prove something like that is not clear to me.]

share|improve this question
1  
I think you had better say exactly why $O(n)$ can be achieved and what this is for in the first place. For one thing, is $k$ fixed? What are you working on, anyway? There is quite a lot of recent work on sums of triangular numbers, but this seems more of an attempt to build an algorithm for some purpose. –  Will Jagy Jan 31 '13 at 17:59
    
People working in, or near, sums of triangular numbers include Ben Kane, B.K Oh, and W.K. Chan's student Anna Haensch, see jointmathematicsmeetings.org/meetings/national/jmm2013/… –  Will Jagy Jan 31 '13 at 18:04
    
Without actually doing careful calculations, the claim that $O(n)$ can be achieved can be seen from the fact that if we choose our triangular numbers as described in the post, $a_1$ will be about square root $n$, $a_2$ will be about fourth root $n$ and so on and since $1/2+1/4+1/8...=1$, we have it. –  user31074 Jan 31 '13 at 18:17
    
Also, $k$ can be anything, I'm only interested in the product of the $a_i$'s. The question comes from attempting to understand an optimisation problem better. –  user31074 Jan 31 '13 at 18:38
1  
My calculation gives $2^{\log_2\log_2n+O(1)}n=O(n\log n)$, in agreement with Erick Wong’s comment. In any case, $n^2$ is too much, as already Gauss’ theorem gives $O(n^{3/2})$. –  Emil Jeřábek Jan 31 '13 at 19:25
show 9 more comments

6 Answers

The sequence $a(n)$ of minimal products (starting, for convenience, at $n=0$), which Will Jagy found to begin

$$1,2,4,3,6,12,4,8,16,12,5,10,\ldots$$

can be defined using the recursion

$$a(n) = \min\left( 2a(n-1),3a(n-3),4a(n-6),5a(n-10)\ldots\right) $$

for $n>0$ (with the understanding that $a(n)$ is undefined for $n<0$). For example,

$$a(11) = \min(2a(10),3a(8),4a(5),5a(1))= \min(10,48,48,10)=10.$$

This should allow a reasonably rapid tabulation up to around $n=10000$.

share|improve this answer
    
Indeed, using Barry's suggestion I find up to 100,000 that some values n have a(n)> 3n, for example a(87050)=312750. I retract my earlier statement that the posters function omega(n) exists. Gerhard "Ask Me About System Design" Paseman, 2013.01.31 –  Gerhard Paseman Jan 31 '13 at 23:59
    
@Gerhard, I found a few with a(n) > 4n. Emil's O(n log n) looks good, though. I had it point out which was the smaller number used in Barry's list version. –  Will Jagy Feb 1 '13 at 1:31
add comment

Up to 100,000,000, the evidence is consistent with $a(n) = o(n \log n).$ However, it is also consistent with the conjecture that $a(n) < 5 n.$ Below are all $n$ such that $a(n) > 4 n,$ for $n < 10^8$.

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

       n      a(n)    k   n - triang     a(n) / n             a(n) / (n log n)
     377      1620    4      26        4.297082228116711        0.7243601861246181
    2409      9776    4    1083        4.058115400581154        0.521141979825834
    2924     11856    4    1328        4.054719562243502        0.5080651557798358
    4457     19552    5      86        4.386807269463765        0.5221002825521364
    5237     21216    5      86        4.051174336452167        0.4730743737436168
    5774     23112    4     103        4.00277104260478        0.4621539565467688
   18695     78744    4     167        4.212035303557101        0.4282259482688222
   36500    153900    5     185        4.216438356164383        0.4013718465190124
   81771    327240    5     365        4.001907766812195        0.3537855116876313
  122697    521235    4     432        4.248147876476198        0.3625481203181061
  487529   2010666    4   10753        4.124197740031875        0.3148938427817576
  708534   3505172    5    2268        4.947076639935416        0.3672402776801521
  743525   3118144    3   54974        4.193731212803874        0.3102065465513547
 1053054   4815972    3  185151        4.573338119412679        0.329795232400189
 1540764   6844500    4    1629        4.44227668870768        0.3117870922046103
 1738022   7705776    4    1706        4.433646984905829        0.308572334234016
 2666783  10844610    4   57313        4.066551346697501        0.2748341420425469
 3051479  13031040    4    7201        4.27040133653222        0.2860064408420606
 4148505  20141484    5    5624        4.855118651176749        0.3186137460305866
 4856214  22366476    4   80619        4.605743486592642        0.2991564294828833
 9297650  37763460    4   33290        4.061613418444446        0.2531345905630797
54262017 219108240    4  145611        4.037967110584924        0.2267331768485826
84959663 343780800    4  179932        4.04640023113086        0.2216272082074552

jagy@phobeusjunior:~$ 
    jagy@phobeusjunior:~$ date
Sat Feb  2    2013

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

share|improve this answer
    
Thanks for sharing your results - It would seem that hoping for $o(n)$ is essentially wishful thinking, though trying to prove that there are infinitely many $n$ for which $a(n)$ is $\Theta(n)$ seems like a hard problem as well. –  user31074 Feb 1 '13 at 9:36
add comment

If $t$ is a triangular number then $8t+1$ is an odd square, and vice versa. So writing $n$ as a sum of $k$ triangular numbers all at least $1$ becomes writing $8m+k$ as a sum of odd squares at least $9$ $$8n+k=\sum_1^k(2c_i+1)^2.$$ I wonder if any insight arises from expressing $N$ as a sum of odd squares so as to minimize $\frac{\prod (2c_i+1)}{N}$ and if the extremes occur at about $8n$ for $n$ extreme to this triangular numbers problem. If so then perhaps some insight is available. If we instead try to minimize $\frac{\prod (c_i)}{N}$ then we have an exact match.

For example the solutions, in increasing increasing order of merit, to $\binom{a}{2}+\binom{b}{2}+\binom{c}{2}=52$ are

$[7,7,5][9,5,4],[8,7,3],[9,6,2],[10,4,2]$ with products $245,180,168,108,80.$

Since $8\cdot52+3=419$ we have that the same triples are the solutions to $(2a+1)^2+(2b+1)^+(2c+1)^2=419$

Alternately the "odd" solutions to $u^2+v^2+w^2=419$ are $[13,13,9],[17,9,7],[15,13,5],[17,11,3],[19,7,3]$ with products $1521, 1071, 975, 561, 399.$

Of course sometime we need to consider $8n+4$ as a sum of four odd squares. So maybe this helps or maybe not. However the extreme cases found so far seem to all come from $3,4$ or $5$ squares. I wonder if that could be proved. If so perhaps the squares perspective would be helpful.

I did not find any of the triangle problem sequences in the OEIS. For example $2, 5, 20, 119, 230, 7259, 26795$ is record breakers for a greedy triangular number partition problem

Consider the sequence $2,2,3,6,21,231,\cdots$ defined by $a_1=a_2=2$ and $a_{k+1}=\binom{a_k+1}{2}$ for $k \ge 2$ Also let $b_i=\binom{a_i}{2}$ and $n_i=\sum_1^ib_j.$ So $n_i$ starts out $2,5,20,230,26795.$ The $n_i$ are half the terms of the sequence I mentioned above, I.E. half the record values of $\frac{\prod{a_i}}{n}$ alternating the lead with the similar series $2, 4, 14, 119, 7259,\cdots$ generated by $2,3,5,15,120.$ (I think this is correct after some initial irregularities, I might be wrong.) By my very rough calculations, $a_i \approx 2^{2^{i-2}}$ while $b_i \approx n_i \approx 2^{2^{i-1}}.$ The greedy algorithm expresses $n_i$ as $\sum_0^ib_j=\sum_0^i \binom{a_i}{2}$ with $\prod a_j \approx \log_2(n_i)n_i$.

share|improve this answer
add comment

Up to 100,000, the program output is consistent with Barry's idea that a(n) is actually $o(n \log n),$ here each is the last occurrence of ratio at least...

=-=-=-=-=-=-=-=-=-=-=

       n      a(n)                  a(n) / (n log n)
       5      12       3       2  1.491203842943068     1.0
       8      16       3       2  0.9617966939259756    0.9
      33      96       4       5  0.8319990327350526    0.8
     377    1620       4      26  0.7243601861246181    0.7
     377    1620       4      26  0.7243601861246181    0.6
    4457   19552       5      86  0.5221002825521364    0.5
   36500  153900       5     185  0.4013718465190124    0.4
   95643  334080       3    1248  0.3045757315691415    0.3 

=-=-=-=-=-=-=-=-=-=-=

Using Barry's description, here are the numbers below 100,000 for which $a(n) > 4n.$

=-=-=-=-=-=-=-=-=-=-=

      n     a(n)       k  n-trianglular       a(n) / n
     377    1620       4     376        4.297082228116711
    2409    9776       4    2408        4.058115400581154
    2924   11856       4    2923        4.054719562243502
    4457   19552       5    4456        4.386807269463765
    5237   21216       5    5236        4.051174336452167
    5774   23112       4    5773        4.00277104260478
   18695   78744       4   18692        4.212035303557101
   36500  153900       5   36499        4.216438356164383
   81771  327240       5   81770        4.001907766812195
jagy@phobeusjunior:~$ 

=-=-=-=-=-=-=-=-=-=-=

Same list, but this time showing the largest triangular number used (as a difference)...

=-=-=-=-=-=-=-=-=-=-=

      n     a(n)       k  n-trianglular       a(n) / n
     377    1620       4      26        4.297082228116711
    2409    9776       4    1083        4.058115400581154
    2924   11856       4    1328        4.054719562243502
    4457   19552       5      86        4.386807269463765
    5237   21216       5      86        4.051174336452167
    5774   23112       4     103        4.00277104260478
   18695   78744       4     167        4.212035303557101
   36500  153900       5     185        4.216438356164383
   81771  327240       5     365        4.001907766812195
jagy@phobeusjunior:~$ 

=-=-=-=-=-=-=-=-=-=-=

This is what I meant about experimenting. I allowed for as many as six triangular numbers, which may or may not really lead to optimum for all targets up to 55, but it seems likely. I told the computer that 1 choose 2 was defined to be 0, so both the product and the sum are unaffected if any of the $a_i$ are given as 1.

Note: from Emil's comment about $n^{3/2},$ it is necessary to run this program up to 1000 or 10000 where $\sqrt n > \log n$ and most targets will have an optimal expression with, say, half a dozen triangular numbers, as opposed to the two or three typical here.

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

best              4           6
best              5          12
best              6           4
best              7           8
best              8          16
best              9          12
best             10           5
best             11          10
best             12          16
best             13          15
best             14          30
best             15           6
best             16          12
best             17          24
best             18          18
best             19          36
best             20          25
best             21           7
best             22          14
best             23          28
best             24          21
best             25          30
best             26          60
best             27          28
best             28           8
best             29          16
best             30          32
best             31          24
best             32          48
best             33          96
best             34          32
best             35          64
best             36           9
best             37          18
best             38          36
best             39          27
best             40          54
best             41         108
best             42          36
best             43          48
best             44          96
best             45          10
best             46          20
best             47          40
best             48          30
best             49          56
best             50         112
best             51          40
best             52          80
best             53         160
best             54         120
best             55          11

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

16         2    2    2    2    1    1         4
6         3    2    1    1    1    1         4
best              4           6

32         2    2    2    2    2    1         5
12         3    2    2    1    1    1         5
best              5          12

64         2    2    2    2    2    2         6
24         3    2    2    2    1    1         6
9         3    3    1    1    1    1         6
4         4    1    1    1    1    1         6
best              6           4

48         3    2    2    2    2    1         7
18         3    3    2    1    1    1         7
8         4    2    1    1    1    1         7
best              7           8

96         3    2    2    2    2    2         8
36         3    3    2    2    1    1         8
16         4    2    2    1    1    1         8
best              8          16

72         3    3    2    2    2    1         9
27         3    3    3    1    1    1         9
32         4    2    2    2    1    1         9
12         4    3    1    1    1    1         9
best              9          12

144         3    3    2    2    2    2        10
54         3    3    3    2    1    1        10
64         4    2    2    2    2    1        10
24         4    3    2    1    1    1        10
5         5    1    1    1    1    1        10
best             10           5

108         3    3    3    2    2    1        11
128         4    2    2    2    2    2        11
48         4    3    2    2    1    1        11
10         5    2    1    1    1    1        11
best             11          10

216         3    3    3    2    2    2        12
81         3    3    3    3    1    1        12
96         4    3    2    2    2    1        12
36         4    3    3    1    1    1        12
16         4    4    1    1    1    1        12
20         5    2    2    1    1    1        12
best             12          16

162         3    3    3    3    2    1        13
192         4    3    2    2    2    2        13
72         4    3    3    2    1    1        13
32         4    4    2    1    1    1        13
40         5    2    2    2    1    1        13
15         5    3    1    1    1    1        13
best             13          15

324         3    3    3    3    2    2        14
144         4    3    3    2    2    1        14
64         4    4    2    2    1    1        14
80         5    2    2    2    2    1        14
30         5    3    2    1    1    1        14
best             14          30

243         3    3    3    3    3    1        15
288         4    3    3    2    2    2        15
108         4    3    3    3    1    1        15
128         4    4    2    2    2    1        15
48         4    4    3    1    1    1        15
160         5    2    2    2    2    2        15
60         5    3    2    2    1    1        15
6         6    1    1    1    1    1        15
best             15           6

486         3    3    3    3    3    2        16
216         4    3    3    3    2    1        16
256         4    4    2    2    2    2        16
96         4    4    3    2    1    1        16
120         5    3    2    2    2    1        16
45         5    3    3    1    1    1        16
20         5    4    1    1    1    1        16
12         6    2    1    1    1    1        16
best             16          12

432         4    3    3    3    2    2        17
192         4    4    3    2    2    1        17
240         5    3    2    2    2    2        17
90         5    3    3    2    1    1        17
40         5    4    2    1    1    1        17
24         6    2    2    1    1    1        17
best             17          24

729         3    3    3    3    3    3        18
324         4    3    3    3    3    1        18
384         4    4    3    2    2    2        18
144         4    4    3    3    1    1        18
64         4    4    4    1    1    1        18
180         5    3    3    2    2    1        18
80         5    4    2    2    1    1        18
48         6    2    2    2    1    1        18
18         6    3    1    1    1    1        18
best             18          18

648         4    3    3    3    3    2        19
288         4    4    3    3    2    1        19
128         4    4    4    2    1    1        19
360         5    3    3    2    2    2        19
135         5    3    3    3    1    1        19
160         5    4    2    2    2    1        19
60         5    4    3    1    1    1        19
96         6    2    2    2    2    1        19
36         6    3    2    1    1    1        19
best             19          36

576         4    4    3    3    2    2        20
256         4    4    4    2    2    1        20
270         5    3    3    3    2    1        20
320         5    4    2    2    2    2        20
120         5    4    3    2    1    1        20
25         5    5    1    1    1    1        20
192         6    2    2    2    2    2        20
72         6    3    2    2    1    1        20
best             20          25

972         4    3    3    3    3    3        21
432         4    4    3    3    3    1        21
512         4    4    4    2    2    2        21
192         4    4    4    3    1    1        21
540         5    3    3    3    2    2        21
240         5    4    3    2    2    1        21
50         5    5    2    1    1    1        21
144         6    3    2    2    2    1        21
54         6    3    3    1    1    1        21
24         6    4    1    1    1    1        21
7         7    1    1    1    1    1        21
best             21           7

864         4    4    3    3    3    2        22
384         4    4    4    3    2    1        22
405         5    3    3    3    3    1        22
480         5    4    3    2    2    2        22
180         5    4    3    3    1    1        22
80         5    4    4    1    1    1        22
100         5    5    2    2    1    1        22
288         6    3    2    2    2    2        22
108         6    3    3    2    1    1        22
48         6    4    2    1    1    1        22
14         7    2    1    1    1    1        22
best             22          14

768         4    4    4    3    2    2        23
810         5    3    3    3    3    2        23
360         5    4    3    3    2    1        23
160         5    4    4    2    1    1        23
200         5    5    2    2    2    1        23
75         5    5    3    1    1    1        23
216         6    3    3    2    2    1        23
96         6    4    2    2    1    1        23
28         7    2    2    1    1    1        23
best             23          28

1296         4    4    3    3    3    3        24
576         4    4    4    3    3    1        24
256         4    4    4    4    1    1        24
720         5    4    3    3    2    2        24
320         5    4    4    2    2    1        24
400         5    5    2    2    2    2        24
150         5    5    3    2    1    1        24
432         6    3    3    2    2    2        24
162         6    3    3    3    1    1        24
192         6    4    2    2    2    1        24
72         6    4    3    1    1    1        24
56         7    2    2    2    1    1        24
21         7    3    1    1    1    1        24
best             24          21

1152         4    4    4    3    3    2        25
512         4    4    4    4    2    1        25
1215         5    3    3    3    3    3        25
540         5    4    3    3    3    1        25
640         5    4    4    2    2    2        25
240         5    4    4    3    1    1        25
300         5    5    3    2    2    1        25
324         6    3    3    3    2    1        25
384         6    4    2    2    2    2        25
144         6    4    3    2    1    1        25
30         6    5    1    1    1    1        25
112         7    2    2    2    2    1        25
42         7    3    2    1    1    1        25
best             25          30

1024         4    4    4    4    2    2        26
1080         5    4    3    3    3    2        26
480         5    4    4    3    2    1        26
600         5    5    3    2    2    2        26
225         5    5    3    3    1    1        26
100         5    5    4    1    1    1        26
648         6    3    3    3    2    2        26
288         6    4    3    2    2    1        26
60         6    5    2    1    1    1        26
224         7    2    2    2    2    2        26
84         7    3    2    2    1    1        26
best             26          60

1728         4    4    4    3    3    3        27
768         4    4    4    4    3    1        27
960         5    4    4    3    2    2        27
450         5    5    3    3    2    1        27
200         5    5    4    2    1    1        27
486         6    3    3    3    3    1        27
576         6    4    3    2    2    2        27
216         6    4    3    3    1    1        27
96         6    4    4    1    1    1        27
120         6    5    2    2    1    1        27
168         7    3    2    2    2    1        27
63         7    3    3    1    1    1        27
28         7    4    1    1    1    1        27
best             27          28

1536         4    4    4    4    3    2        28
1620         5    4    3    3    3    3        28
720         5    4    4    3    3    1        28
320         5    4    4    4    1    1        28
900         5    5    3    3    2    2        28
400         5    5    4    2    2    1        28
972         6    3    3    3    3    2        28
432         6    4    3    3    2    1        28
192         6    4    4    2    1    1        28
240         6    5    2    2    2    1        28
90         6    5    3    1    1    1        28
336         7    3    2    2    2    2        28
126         7    3    3    2    1    1        28
56         7    4    2    1    1    1        28
8         8    1    1    1    1    1        28
best             28           8

1440         5    4    4    3    3    2        29
640         5    4    4    4    2    1        29
675         5    5    3    3    3    1        29
800         5    5    4    2    2    2        29
300         5    5    4    3    1    1        29
864         6    4    3    3    2    2        29
384         6    4    4    2    2    1        29
480         6    5    2    2    2    2        29
180         6    5    3    2    1    1        29
252         7    3    3    2    2    1        29
112         7    4    2    2    1    1        29
16         8    2    1    1    1    1        29
best             29          16

2304         4    4    4    4    3    3        30
1024         4    4    4    4    4    1        30
1280         5    4    4    4    2    2        30
1350         5    5    3    3    3    2        30
600         5    5    4    3    2    1        30
125         5    5    5    1    1    1        30
1458         6    3    3    3    3    3        30
648         6    4    3    3    3    1        30
768         6    4    4    2    2    2        30
288         6    4    4    3    1    1        30
360         6    5    3    2    2    1        30
36         6    6    1    1    1    1        30
504         7    3    3    2    2    2        30
189         7    3    3    3    1    1        30
224         7    4    2    2    2    1        30
84         7    4    3    1    1    1        30
32         8    2    2    1    1    1        30
best             30          32

2048         4    4    4    4    4    2        31
2160         5    4    4    3    3    3        31
960         5    4    4    4    3    1        31
1200         5    5    4    3    2    2        31
250         5    5    5    2    1    1        31
1296         6    4    3    3    3    2        31
576         6    4    4    3    2    1        31
720         6    5    3    2    2    2        31
270         6    5    3    3    1    1        31
120         6    5    4    1    1    1        31
72         6    6    2    1    1    1        31
378         7    3    3    3    2    1        31
448         7    4    2    2    2    2        31
168         7    4    3    2    1    1        31
35         7    5    1    1    1    1        31
64         8    2    2    2    1    1        31
24         8    3    1    1    1    1        31
best             31          24

1920         5    4    4    4    3    2        32
2025         5    5    3    3    3    3        32
900         5    5    4    3    3    1        32
400         5    5    4    4    1    1        32
500         5    5    5    2    2    1        32
1152         6    4    4    3    2    2        32
540         6    5    3    3    2    1        32
240         6    5    4    2    1    1        32
144         6    6    2    2    1    1        32
756         7    3    3    3    2    2        32
336         7    4    3    2    2    1        32
70         7    5    2    1    1    1        32
128         8    2    2    2    2    1        32
48         8    3    2    1    1    1        32
best             32          48

3072         4    4    4    4    4    3        33
1800         5    5    4    3    3    2        33
800         5    5    4    4    2    1        33
1000         5    5    5    2    2    2        33
375         5    5    5    3    1    1        33
1944         6    4    3    3    3    3        33
864         6    4    4    3    3    1        33
384         6    4    4    4    1    1        33
1080         6    5    3    3    2    2        33
480         6    5    4    2    2    1        33
288         6    6    2    2    2    1        33
108         6    6    3    1    1    1        33
567         7    3    3    3    3    1        33
672         7    4    3    2    2    2        33
252         7    4    3    3    1    1        33
112         7    4    4    1    1    1        33
140         7    5    2    2    1    1        33
256         8    2    2    2    2    2        33
96         8    3    2    2    1    1        33
best             33          96

2880         5    4    4    4    3    3        34
1280         5    4    4    4    4    1        34
1600         5    5    4    4    2    2        34
750         5    5    5    3    2    1        34
1728         6    4    4    3    3    2        34
768         6    4    4    4    2    1        34
810         6    5    3    3    3    1        34
960         6    5    4    2    2    2        34
360         6    5    4    3    1    1        34
576         6    6    2    2    2    2        34
216         6    6    3    2    1    1        34
1134         7    3    3    3    3    2        34
504         7    4    3    3    2    1        34
224         7    4    4    2    1    1        34
280         7    5    2    2    2    1        34
105         7    5    3    1    1    1        34
192         8    3    2    2    2    1        34
72         8    3    3    1    1    1        34
32         8    4    1    1    1    1        34
best             34          32

2560         5    4    4    4    4    2        35
2700         5    5    4    3    3    3        35
1200         5    5    4    4    3    1        35
1500         5    5    5    3    2    2        35
1536         6    4    4    4    2    2        35
1620         6    5    3    3    3    2        35
720         6    5    4    3    2    1        35
150         6    5    5    1    1    1        35
432         6    6    3    2    2    1        35
1008         7    4    3    3    2    2        35
448         7    4    4    2    2    1        35
560         7    5    2    2    2    2        35
210         7    5    3    2    1    1        35
384         8    3    2    2    2    2        35
144         8    3    3    2    1    1        35
64         8    4    2    1    1    1        35
best             35          64

4096         4    4    4    4    4    4        36
2400         5    5    4    4    3    2        36
1125         5    5    5    3    3    1        36
500         5    5    5    4    1    1        36
2592         6    4    4    3    3    3        36
1152         6    4    4    4    3    1        36
1440         6    5    4    3    2    2        36
300         6    5    5    2    1    1        36
864         6    6    3    2    2    2        36
324         6    6    3    3    1    1        36
144         6    6    4    1    1    1        36
1701         7    3    3    3    3    3        36
756         7    4    3    3    3    1        36
896         7    4    4    2    2    2        36
336         7    4    4    3    1    1        36
420         7    5    3    2    2    1        36
42         7    6    1    1    1    1        36
288         8    3    3    2    2    1        36
128         8    4    2    2    1    1        36
9         9    1    1    1    1    1        36
best             36           9

3840         5    4    4    4    4    3        37
2250         5    5    5    3    3    2        37
1000         5    5    5    4    2    1        37
2304         6    4    4    4    3    2        37
2430         6    5    3    3    3    3        37
1080         6    5    4    3    3    1        37
480         6    5    4    4    1    1        37
600         6    5    5    2    2    1        37
648         6    6    3    3    2    1        37
288         6    6    4    2    1    1        37
1512         7    4    3    3    3    2        37
672         7    4    4    3    2    1        37
840         7    5    3    2    2    2        37
315         7    5    3    3    1    1        37
140         7    5    4    1    1    1        37
84         7    6    2    1    1    1        37
576         8    3    3    2    2    2        37
216         8    3    3    3    1    1        37
256         8    4    2    2    2    1        37
96         8    4    3    1    1    1        37
18         9    2    1    1    1    1        37
best             37          18

3600         5    5    4    4    3    3        38
1600         5    5    4    4    4    1        38
2000         5    5    5    4    2    2        38
2160         6    5    4    3    3    2        38
960         6    5    4    4    2    1        38
1200         6    5    5    2    2    2        38
450         6    5    5    3    1    1        38
1296         6    6    3    3    2    2        38
576         6    6    4    2    2    1        38
1344         7    4    4    3    2    2        38
630         7    5    3    3    2    1        38
280         7    5    4    2    1    1        38
168         7    6    2    2    1    1        38
432         8    3    3    3    2    1        38
512         8    4    2    2    2    2        38
192         8    4    3    2    1    1        38
40         8    5    1    1    1    1        38
36         9    2    2    1    1    1        38
best             38          36

3200         5    5    4    4    4    2        39
3375         5    5    5    3    3    3        39
1500         5    5    5    4    3    1        39
3456         6    4    4    4    3    3        39
1536         6    4    4    4    4    1        39
1920         6    5    4    4    2    2        39
900         6    5    5    3    2    1        39
972         6    6    3    3    3    1        39
1152         6    6    4    2    2    2        39
432         6    6    4    3    1    1        39
2268         7    4    3    3    3    3        39
1008         7    4    4    3    3    1        39
448         7    4    4    4    1    1        39
1260         7    5    3    3    2    2        39
560         7    5    4    2    2    1        39
336         7    6    2    2    2    1        39
126         7    6    3    1    1    1        39
864         8    3    3    3    2    2        39
384         8    4    3    2    2    1        39
80         8    5    2    1    1    1        39
72         9    2    2    2    1    1        39
27         9    3    1    1    1    1        39
best             39          27

5120         5    4    4    4    4    4        40
3000         5    5    5    4    3    2        40
625         5    5    5    5    1    1        40
3072         6    4    4    4    4    2        40
3240         6    5    4    3    3    3        40
1440         6    5    4    4    3    1        40
1800         6    5    5    3    2    2        40
1944         6    6    3    3    3    2        40
864         6    6    4    3    2    1        40
180         6    6    5    1    1    1        40
2016         7    4    4    3    3    2        40
896         7    4    4    4    2    1        40
945         7    5    3    3    3    1        40
1120         7    5    4    2    2    2        40
420         7    5    4    3    1    1        40
672         7    6    2    2    2    2        40
252         7    6    3    2    1    1        40
648         8    3    3    3    3    1        40
768         8    4    3    2    2    2        40
288         8    4    3    3    1    1        40
128         8    4    4    1    1    1        40
160         8    5    2    2    1    1        40
144         9    2    2    2    2    1        40
54         9    3    2    1    1    1        40
best             40          54

4800         5    5    4    4    4    3        41
1250         5    5    5    5    2    1        41
2880         6    5    4    4    3    2        41
1350         6    5    5    3    3    1        41
600         6    5    5    4    1    1        41
1728         6    6    4    3    2    2        41
360         6    6    5    2    1    1        41
1792         7    4    4    4    2    2        41
1890         7    5    3    3    3    2        41
840         7    5    4    3    2    1        41
175         7    5    5    1    1    1        41
504         7    6    3    2    2    1        41
1296         8    3    3    3    3    2        41
576         8    4    3    3    2    1        41
256         8    4    4    2    1    1        41
320         8    5    2    2    2    1        41
120         8    5    3    1    1    1        41
288         9    2    2    2    2    2        41
108         9    3    2    2    1    1        41
best             41         108

4500         5    5    5    4    3    3        42
2000         5    5    5    4    4    1        42
2500         5    5    5    5    2    2        42
4608         6    4    4    4    4    3        42
2700         6    5    5    3    3    2        42
1200         6    5    5    4    2    1        42
2916         6    6    3    3    3    3 
share|improve this answer
    
Seems to have cropped the longer table in the middle of target 43. –  Will Jagy Jan 31 '13 at 22:19
    
Will, maybe the appropriate ratio to consider is $a(n)/n\ln n$. Note that for the two "record" ratios for $a(n)/n$ at $n=377$ and $n=4457$, one has $1620/377\ln377 \approx 0.72436$ and $19552/4457\ln4457 \approx 0.52210$. Could the $O(n\ln n)$ bound be improved to $o(n\ln n)$? –  Barry Cipra Feb 1 '13 at 1:54
    
@Barry, yes, I put in some data, the last time a(n) / (n log n) is at least 1.0 or 0.9 or... or 0.3 which was still going strong at 100,000. So your idea of little o(n log n) looks good. –  Will Jagy Feb 1 '13 at 2:21
add comment

For $n < 100,000,000$ the numbers with $a(n) > 3.5 n.$

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

        n          a(n)   k  (n - trangular)    a(n) / n
       377        1620    4        26        4.297082228116711
       944        3552    4       278        3.76271186440678
      2409        9776    4      1083        4.058115400581154
      2924       11856    4      1328        4.054719562243502
      3134       11680    3       506        3.726866624122527
      4457       19552    5        86        4.386807269463765
      4551       18000    3      1776        3.955174686882004
      4937       17848    3       281        3.615150901357099
      5237       21216    5        86        4.051174336452167
      5339       19836    4      1598        3.715302491103203
      5774       23112    4       103        4.00277104260478
      7007       24570    4       221        3.506493506493507
      7743       29760    4       117        3.843471522665634
      8119       28575    4       118        3.519522108634068
      8643       31347    3       387        3.626865671641791
     17951       63640    3       931        3.545206395186898
     18695       78744    4       167        4.212035303557101
     19280       71344    4       170        3.700414937759336
     21695       84864    4       167        3.911684719981563
     22322       86088    4       167        3.85664366992205
     22364       82836    4      6788        3.703988553031658
     23862       86328    4       209        3.617802363590646
     28154      103132    3       424        3.66313845279534
     29105      113760    4      1139        3.908606768596461
     31106      115320    4       478        3.707323345978268
     31354      110592    3      8134        3.52720546022836
     34683      138075    4       230        3.981057001989447
     36500      153900    5       185        4.216438356164383
     37080      142788    3     13209        3.850809061488673
     43301      154350    4       230        3.564582804092284
     46545      164112    4     12092        3.525878182404125
     48786      172224    5       270        3.530193088181035
     53945      196800    5       317        3.648160163129113
     71945      268560    4      2567        3.732851483772326
     81771      327240    5       365        4.001907766812195
     87050      312750    5       314        3.592762780011488
    112478      420432    4      6448        3.737904301285585
    113024      427500    5       449        3.782382502831257
    119765      440100    5       449        3.674696280215422
    122697      521235    4       432        4.248147876476198
    122757      429660    4       492        3.500085534837117
    146025      535680    5       495        3.668412942989214
    153005      579420    4     17024        3.786935067481455
    171965      611784    4       560        3.55760765272003
    199989      776286    3     16674        3.881643490391971
    210653      741312    4      1025        3.519114372926092
    218744      768840    3     11054        3.514793548623048
    306845     1074480    3     43670        3.501702814124395
    319178     1170180    3      9100        3.666230128642952
    339768     1341280    3     13740        3.947634856725766
    358658     1372140    5       377        3.825761589034679
    364041     1373664    4    120788        3.773377174549021
    381404     1354792    3     19729        3.552117964153496
    487529     2010666    4     10753        4.124197740031875
    487577     1820280    4      2957        3.733318019512815
    488474     1729000    4       896        3.539594737898025
    488507     1835820    4      1916        3.758021891190914
    497495     1838172    4    152630        3.694855224675625
    499479     1760472    5      1976        3.524616650549873
    530711     1975548    4    167333        3.722455347637415
    562259     2238720    4       989        3.981652583595816
    578204     2100612    4    167333        3.632994583226681
    613193     2156700    4      2128        3.517163437938789
    614294     2260830    4      4334        3.680371288015185
    619904     2302944    4     11048        3.715001032417923
    628836     2206344    3    162741        3.508615918935939
    631124     2225040    3     32159        3.525519549248642
    644321     2531088    5      1910        3.928302818005311
    648078     2397933    3      2262        3.700068510271912
    657074     2349540    3      2134        3.57576163415384
    708534     3505172    5      2268        4.947076639935416
    710774     2493556    4    183923        3.508226243503561
    743525     3118144    3     54974        4.193731212803874
    800605     2912328    4     18730        3.637659020365848
    826139     3027460    4      1169        3.664589130884754
    831102     3008580    4     83849        3.619988882231062
    853241     3113928    4    250988        3.649529265471303
    873014     3069730    3    125761        3.516243725759266
    887654     3132864    5      1208        3.529375184475032
    913079     3450600    5      2504        3.77908154716076
    944576     3385536    4      1325        3.584185920455315
    950129     3662880    3    172001        3.855139670507899
   1023154     3583932    3      2848        3.502827531339368
   1053054     4815972    3    185151        4.573338119412679
   1069145     4198272    4    430130        3.926756426864457
   1125620     4101264    5      2869        3.643559993603525
   1194260     4374720    4     41339        3.663121933247367
   1433870     5073000    4      4975        3.537977640929792
   1437092     5030760    4      1427        3.500652706994403
   1532012     5488000    4      1637        3.582217371665496
   1540764     6844500    4      1629        4.44227668870768
   1546109     5569360    3    236338        3.602178112927355
   1574189     5747760    5      1538        3.651251533329225
   1728807     6313800    3      5511        3.652113856549632
   1738022     7705776    4      1706        4.433646984905829
   1756593     6184200    5      1592        3.520565093906215
   2101988     7656960    4    114967        3.642722984146437
   2162096     8304000    3      8246        3.840717525956294
   2392571     8396850    4     15281        3.50955102272827
   2514050     9026292    5      1889        3.59033909429009
   2566235     9526600    3    422750        3.712286676785252
   2606609     9437922    4      1706        3.620766290609754
   2666783    10844610    4     57313        4.066551346697501
   2726700     9582840    4      1755        3.51444603366707
   2943915    11066720    4     41070        3.759184623197341
   2955869    10405836    4      7063        3.520398231450717
   3051479    13031040    4      7201        4.27040133653222
   3148760    11146122    3      7489        3.539844891322298
   3199064    12361752    4      2408        3.864177771998309
   3785324    14553280    3    681538        3.844659004090535
   4148505    20141484    5      5624        4.855118651176749
   4160028    16131140    3    765713        3.877651785036062
   4278428    15179472    4    221452        3.547908717874883
   4417170    15758184    4      5235        3.567484158409117
   4555499    16685504    5     14908        3.66271708104864
   4570599    17266730    3     57089        3.777782737011057
   4713605    18242700    3     14960        3.870222473032848
   4856214    22366476    4     80619        4.605743486592642
   4918508    18635400    4     15362        3.788831897803155
   5111928    19120640    4    296072        3.740396969597381
   5237153    19183008    4      2923        3.662869501807566
   5609519    20335128    4      3293        3.62511081609671
   5791500    20667474    4     57309        3.568587412587413
   5828400    22007024    4      5822        3.775825955665363
   5921345    20997760    4      6265        3.546113256363208
   5977013    21814375    3    944635        3.649711820937984
   6060230    22278400    4      3290        3.676164105982776
   6377159    24006312    4     20764        3.764421116048698
   6539531    25291444    3     21676        3.867470618305808
   6736259    24628800    4     21979        3.656153957263223
   7278935    25518432    4    685039        3.505791987426732
   7401413    26275872    4      7478        3.55011563332569
   7590987    29577240    4     65727        3.896362884036029
   7933785    28037850    5     27509        3.533981573738134
   8750180    32834112    5     53645        3.752392750777698
   8914607    32087200    4      4076        3.59939591279795
   9297650    37763460    4     33290        4.061613418444446
   9346322    36235648    4      8641        3.87699546409807
   9526839    35421234    4     28578        3.718046877878381
  10271700    37488704    4      4454        3.649707838040441
  10293233    36452388    3    228892        3.541393457235448
  10700699    41116075    3    877171        3.842372820691433
  10830575    39205296    6      3044        3.619872075120665
  10887764    38109696    4    236344        3.500231636174333
  10892754    39281112    4     23301        3.606169018413525
  11297264    41553600    5    150983        3.678200314695665
  11570390    40535112    4   2990237        3.50334880673858
  11607968    44046648    4      8632        3.794518385991415
  12697697    49261264    5      4456        3.87954319590395
  13381514    48341685    4      4136        3.612572164853693
  13501710    50516180    4     10295        3.741465340316152
  14685092    54864474    3   1595806        3.736066072994299
  15072318    54310326    3     21477        3.603316092455056
  15264369    54455592    3      9843        3.567497090773946
  16014350    60271750    3    588115        3.763608888278325
  17543358    65887452    3      5355        3.755692154261459
  17768331    66752000    4     10511        3.756796291109165
  18092546    65058240    5      5441        3.595858758629106
  18594675    66302250    3    266190        3.565657910127496
  18625892    67320000    4    628892        3.614323544880428
  19048806    69817664    5      5100        3.665198963126613
  21063119    77693616    4    148841        3.688609270070591
  21256397    76865200    4     43556        3.616097309435837
  22554933    79237704    4    493530        3.513098620155511
  23093774    82862832    4   6438668        3.588102663514417
  25116125    92868048    5      6884        3.69754681504412
  25542609    90452432    5      6378        3.541236997363895
  26052704    95841760    4     13768        3.678764400040779
  26109692    94424640    4    214886        3.616459359229515
  26516996    98940000    4     57821        3.73119187407201
  27095031   101537634    4      6551        3.747463289486548
  27486656   103165810    4      6665        3.753305240186365
  27724950    97894820    4   7344030        3.530928640087719
  27790965   102439944    3   8493387        3.686088050558878
  27948929    98012200    3     14854        3.506832050702193
  30642003   109327536    3     14952        3.567897829655588
  31366983   110739296    3     15662        3.530441419884086
  31660668   117679797    3    150777        3.716908215581554
  32678023   117534903    3     14620        3.596756847866837
  34051070   119893374    4    328492        3.520986976327029
  34656740   123431424    3    107912        3.561541679915653
  38501162   142436148    3    250531        3.699528549294175
  40919563   146480400    4     45202        3.579715648478455
  42757394   150734844    5     45491        3.525351521657283
  43659675   160492544    4      9179        3.67599035036335
  46971593   170623242    4    482690        3.632477229375636
  54262017   219108240    4    145611        4.037967110584924
  57969450   206383044    4    419094        3.560203589994385
  61188365   218122920    3     21035        3.564777715501958
  68917241   245462490    5     21050        3.561699314109223
  69411164   244629060    4     56411        3.524347466640957
  72437318   265728532    3  21770107        3.668392747506195
  73247012   259686240    4    579472        3.545349262847746
  73900616   262277748    4  19898588        3.549060375897273
  84116339   300673704    5   1908086        3.574498219662175
  84959663   343780800    4    179932        4.04640023113086
  87521729   311169600    4     11894        3.555341097066307
        n          a(n)   k  (n - trangular)    a(n) / n

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

share|improve this answer
add comment

I checked out to $50000$ and was tempted by the fact that the record up to there was way back at $4457$. Glad I did not make a bold conjecture. Here are Will's over 4 records in sorted order

       n      a(n)    k   n - triang     a(n) / n             a(n) / (n log n)
  708534   3505172    5    2268        4.947076639935416        0.36724027768
 4148505  20141484    5    5624        4.855118651176749        0.31861374603
 4856214  22366476    4   80619        4.605743486592642        0.29915642948
 1053054   4815972    3  185151        4.573338119412679        0.32979523240
 1540764   6844500    4    1629        4.44227668870768         0.31178709220
 1738022   7705776    4    1706        4.433646984905829        0.30857233423
    4457     19552    5      86        4.386807269463765        0.52210028255
     377      1620    4      26        4.297082228116711        0.72436018612
 3051479  13031040    4    7201        4.27040133653222         0.28600644084
  122697    521235    4     432        4.248147876476198        0.36254812031
   36500    153900    5     185        4.216438356164383        0.40137184651
   18695     78744    4     167        4.212035303557101        0.42822594826
  743525   3118144    3   54974        4.193731212803874        0.31020654655
  487529   2010666    4   10753        4.124197740031875        0.31489384278
 2666783  10844610    4   57313        4.066551346697501        0.27483414204
 9297650  37763460    4   33290        4.061613418444446        0.25313459056
    2409      9776    4    1083        4.058115400581154        0.52114197982
    2924     11856    4    1328        4.054719562243502        0.50806515577
    5237     21216    5      86        4.051174336452167        0.47307437374
84959663 343780800    4  179932        4.04640023113086         0.22162720820
54262017 219108240    4  145611        4.037967110584924        0.22673317684
    5774     23112    4     103        4.00277104260478         0.46215395654
   81771    327240    5     365        4.001907766812195        0.35378551168

And for what it is worth, below is the graph up to 25000. The average seems to be falling and there are hints of structure but not strong ones. alt text

share|improve this answer
    
Hi, Aaron. The count of $n$ with $a(n) > 3.5 n$ per 10,000,000 seems pretty clearly shrinking...so, it may be that $a(n) = o(n)$ which is what he wanted in the first place, it is just extremely slow if true. Plus, proving anything requires looking very carefully at some pattern which may be far from the optima up to $10^8.$ –  Will Jagy Feb 2 '13 at 23:35
    
Agreed. Here are the counts for over 3.5 and over 4.0 in the range from $10^{k-1}$ to $10^k$ -->$[3, 2, 1], [4, 13, 5], [5, 21, 3], [6, 46, 4], [7, 57, 8], [8, 58, 2]$<-- But I would not hazard to say what happens from $10^8$ to $10^9$ –  Aaron Meyerowitz Feb 3 '13 at 0:48
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.