Looking at Don's first paragraph, it seems he is trying to generate
triplets of unique numbers rather than unique triplets of numbers. I
haven't looked at the code.
Henry Rich
On 5/20/2018 10:24 AM, Roger Hui wrote:
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
---
This email has been checked for viruses by AVG.
http://www.avg.com
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
