# Representations with Triangular Numbers

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.]

-
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
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

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$.

-
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

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


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

-
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

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$.

-

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

-
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

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


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

-

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.

-
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