As others noted, the idiom for "n where f(n) is maximal" is (i.>./), which
construct is supported by special code [1] (ie fast).
Also, you might be interested in the dyad p:, whose left domain (left hand
argument) is a range of numeric function codes, which give you access to a
variety of common calculations related to primes, including the totient:
(i. >./)@(% 5&p:) i. 1000000
510510
In fact, this builtin totient function, 5&p:, is also supported by special code
[2], so it should be a lot faster than (-~:)&.q: (though I didn't run any
benchmarks).
-Dan
[1] Special code support and benchmarks for index-of-optimum hooks (like (i.
>./) ):
http://www.jsoftware.com/docs/help701/release/idotmaxmin.htm
[2] Special code support & benchmarks for totient (5&p:):
http://www.jsoftware.com/docs/help701/release/totient.htm
Please excuse typos; sent from a phone.
> On Jun 12, 2014, at 1:37 AM, Jon Hough <[email protected]> wrote:
>
> Another Project Euler...
>
> This time PE #69: http://projecteuler.net/problem=69
>
> Essentially, find n which has the maximum of n/totient(n), for all positive
> integers, n, up to 1000000.
>
> At first this seemed easy. I have a verb to calculate the ratio:
> totient=: (- ~:)&.q:
> func =. ] % totient
> then I can find the maximum:
> max=. (>./)"1@:((] % totient)"0)
>
> max 1+i.1000000
> 5.53939
> But this gives me the ratio. I need to find n.
> This is a problem, because finding the maximum, the verb, >./ , collapsed the
> array so I don't think I can use I. or similar verb to get the index which
> gave the maximum ratio. So I am not sure how to find the n which gave this
> ratio.
>
> A second issue is I think my method seems to not be well thought out
> memory-wise. My method first calculates the ratio for every integer up to 1
> million and holds them all in memory. Surely a better way would be to do them
> one at a time and find the maximum as we go.
> In J I am not sure how to do this. I am guessing the recursion verb $: will
> need to be used.
> Any help appreciated.
> Regards.
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
