The number of triplets is the number of size 3 partitions of 1e6. Using
the function in
http://code.jsoftware.com/wiki/Essays/Partitions#Partitions_with_k_Parts
pnk=: 4 : 0 " 0
n=. 0>.x [ k=. y
if. 1>:n<.k do. x: (0<n)*1=k else. ((n-1) pnk k-1) + (n-k) pnk k end.
)
1e2 pnk 3
833
1e3 pnk 3
83333
1e4 pnk 3
8333333
1e6 pnk 3
|stack error: pnk
| ((n-1)pnk k-1)+(n-k) pnk k
Judging by the progression, the answer is probably 83333333333. Going by
first principles,
n pnk k ←→ ((n-1) pnk k-1) + (n-k) pnk k
Therefore,
n pnk 3 ←→ ((n-1) pnk 2) + (n-3) pnk 3
←→ (<.(n-1)%2) + (n-3) pnk 3
←→ +/ <.@(%&2)@<: n - 3*i.<.n-3
+/ <.@(%&2)@<: n - 3*i.<.n-3 [ n=: 1e2
833
+/ <.@(%&2)@<: n - 3*i.<.n-3 [ n=: 1e3
83333
+/ <.@(%&2)@<: n - 3*i.<.n-3 [ n=: 1e4
8333333
+/ <.@(%&2)@<: n - 3*i.<.n-3 [ n=: 1e5
833333333
+/ <.@(%&2)@<: n - 3*i.<.n-3 [ n=: 1e6
83333333333
On Sat, May 19, 2018 at 1:43 PM, Skip Cave <[email protected]> wrote:
> Another interesting quora problem:
>
> How many distinct triplets have a sum of 1,000,000 (provided all numbers
> are integers and are positive)?
> <https://www.quora.com/qemail/track_click?al_imp=
> eyJ0eXBlIjogMzUsICJoYXNoIjogMTcxMDQ0NjU4Mn0%3D&al_pri=
> QuestionLinkClickthrough&aoid=oMo937UDzj8&aoty=2&aty=4&click_pos=1&ct=
> 1526747413834671&et=103&id=62216bf7b30d40aea1d79bf4401c83
> 17&request_id=289&src=1&st=1526747413838426&stories=
> 2518686273&uid=bqluVqSeN78&v=0>
>
> The obvious straightforward solution would be to use the odometer verb:
>
> odo=: #: i.@(*/)
>
> 1e6=+/"1 odo 3#1e6
>
> |limit error: odo
>
> | 1000000=+/"1 odo 3#1000000
>
>
> Ooops. Unfortunately, I don't have near enough memory to use this approach.
>
> Any suggestions?
>
>
> Skip
>
>
>
> Skip Cave
> Cave Consulting LLC
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
