There is a mistake in your derivation somewhere, because: Using the code in http://code.jsoftware.com/wiki/Essays/Partitions :
t=: part 10 $t 42 7 6$t ┌───────────┬───────────┬─────────────┬───────────────┬─────────────────┬───────────────────┐ │10 │9 1 │8 2 │8 1 1 │7 3 │7 2 1 │ ├───────────┼───────────┼─────────────┼───────────────┼─────────────────┼───────────────────┤ │7 1 1 1 │6 4 │6 3 1 │6 2 2 │6 2 1 1 │6 1 1 1 1 │ ├───────────┼───────────┼─────────────┼───────────────┼─────────────────┼───────────────────┤ │5 5 │5 4 1 │5 3 2 │5 3 1 1 │5 2 2 1 │5 2 1 1 1 │ ├───────────┼───────────┼─────────────┼───────────────┼─────────────────┼───────────────────┤ │5 1 1 1 1 1│4 4 2 │4 4 1 1 │4 3 3 │4 3 2 1 │4 3 1 1 1 │ ├───────────┼───────────┼─────────────┼───────────────┼─────────────────┼───────────────────┤ │4 2 2 2 │4 2 2 1 1 │4 2 1 1 1 1 │4 1 1 1 1 1 1 │3 3 3 1 │3 3 2 2 │ ├───────────┼───────────┼─────────────┼───────────────┼─────────────────┼───────────────────┤ │3 3 2 1 1 │3 3 1 1 1 1│3 2 2 2 1 │3 2 2 1 1 1 │3 2 1 1 1 1 1 │3 1 1 1 1 1 1 1 │ ├───────────┼───────────┼─────────────┼───────────────┼─────────────────┼───────────────────┤ │2 2 2 2 2 │2 2 2 2 1 1│2 2 2 1 1 1 1│2 2 1 1 1 1 1 1│2 1 1 1 1 1 1 1 1│1 1 1 1 1 1 1 1 1 1│ └───────────┴───────────┴─────────────┴───────────────┴─────────────────┴───────────────────┘ +/ 3 = #&> t 8 t #~ 3=#&>t ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐ │8 1 1│7 2 1│6 3 1│6 2 2│5 4 1│5 3 2│4 4 2│4 3 3│ └─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘ But: triplescount 10 5 On Sun, May 20, 2018 at 6:47 AM, Don Guinn <dongu...@gmail.com> wrote: > Couldn't sleep last night so as often, worked on problems. > > Never saw the actually Quora problem, but as I understand it it wants all > unique positive integers that add to 1000000. So far it looks like people > are trying to generate all possible number triples and keeping only those > that add to 1e6. I thought that instead, only generate triples that add to > some number. > > First, the order of the numbers is insignificant. And as unique there must > be a smallest number, a largest and one in between. For some sum n, call > the smallest n1, the middle one n2 and the largest n3. Then set limits for > possible values of n1, n2 and n3. > > As lower limits the minimum value of n1 is 1, n2 is 2 and n3 is3. The > maximum value for n1 must be less than one third of n because n1+n2+n3 must > equal n. > > n1+(n1+1)+(n1+2) <--> (3+3*n1) <: n > > For simplicity, try > > n=:20 > <.n%3 > 6 > > But if n1 is 6 then the three numbers must be at least 6+7+8, or 21. So > n1max must be one less. > > ]n1max=:<:<.n%3 > 5 > > and the possible values for n1 are > > ]n1=:>:i.n1max > 1 2 3 4 5 > > Now n3 is determined by the n-n1+n2 n3 is easy to determine once n1 and n2 > are set. > > For a given value for n1, the possible values for n2 are less than half the > n-n1. > > <.-:n-n1 > 9 9 8 8 7 > > For n1 = 1 the value of 9 works for n2 as the number triple would be > 20=1+9+10 . But for n1 = 2 the result would be 2+9+10 or 21. Too big. So > for some n1, n2max would be > > ]n2max=:<:>.-:n-n1 > 9 8 8 7 7 > > So for each value of n1 n2 has possible values as shown by > > (<"0 n1),.([:}.>:@i.)&.><:>.-:n-n1 > +-+---------------+ > |1|2 3 4 5 6 7 8 9| > +-+---------------+ > |2|2 3 4 5 6 7 8 | > +-+---------------+ > |3|2 3 4 5 6 7 8 | > +-+---------------+ > |4|2 3 4 5 6 7 | > +-+---------------+ > |5|2 3 4 5 6 7 | > +-+---------------+ > > So this is a list of possible values for n1 and n2 > > ]n1n2=:;(<"0 n1),/"0&.>([:}.>:@i.)&.><:>.-:n-n1 > 1 2 > 1 3 > 1 4 > 1 5 > 1 6 > 1 7 > 1 8 > 1 9 > 2 2 > 2 3 > 2 4 > 2 5 > 2 6 > 2 7 > 2 8 > 3 2 > 3 3 > 3 4 > 3 5 > 3 6 > 3 7 > 3 8 > 4 2 > 4 3 > 4 4 > 4 5 > 4 6 > 4 7 > 5 2 > 5 3 > 5 4 > 5 5 > 5 6 > 5 7 > > And possible triple sums for n=20 are > > n1n2,.n-+/"1 n1n2 > 1 2 17 > 1 3 16 > 1 4 15 > 1 5 14 > 1 6 13 > 1 7 12 > 1 8 11 > 1 9 10 > 2 2 16 > 2 3 15 > 2 4 14 > 2 5 13 > 2 6 12 > 2 7 11 > 2 8 10 > 3 2 15 > 3 3 14 > 3 4 13 > 3 5 12 > 3 6 11 > 3 7 10 > 3 8 9 > 4 2 14 > 4 3 13 > 4 4 12 > 4 5 11 > 4 6 10 > 4 7 9 > 5 2 13 > 5 3 12 > 5 4 11 > 5 5 10 > 5 6 9 > 5 7 8 > > ~.+/"1 n1n2,.n-+/"1 n1n2 > 20 > > Needless to say that trying to generate all the possible triples for 1e6 is > still too big. But if all we need is the count, the number of possible n2's > for all n1's is all we need. > > triplescount=:3 : 0 > n1max=.<:<.y%3 > n1=.>:i.n1max > n2max=.<:>.-:y-n1 > +/<:n2max > ) > > triplescount 1e6 > 138887777780 > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
