Don't let the Euler moderators catch your spoiler,
Boyko!
That said, I don't recommend reading the following if
you want to solve Euler 73 completely from cold.
FWIW, the following verb, sumq, seems to run in time
of order O(n) for problem-sizes commensurate with
Problem number 73.
It will of course hit the performance buffers at some
larger scale.
It exploits what I have discovered to be a Möbius
Transform, a technique which comes in useful in
several Euler problems.
NB. number of coprimes to y in open interval (2y, 3y)
NB. subject to coprimes <: x
sumq =: 3 : 0 " 0
:
lim =. x <. _1 0 + 3 2 * y
muf =. mu f =. }. allmufactors y
(-/lim) + +/ muf * -/ <.lim %/ f
)
NB. The totient function, 5&p:, is related, and should
NB. perhaps be exploited here, though I couldn't see how
NB. to get the limits right.
NB. Möbius fn mu(n) is
NB. { 0 if n has one (or more) repeated prime factors
NB. mu(n) = { 1 if n = 1
NB. { (-1)^k if n is product of k distinct non-repeated primes
NB.
mu =: 3 : 0
b =. y > 1
(-.b) + ((#(=*_1^])#@~. )@:q:"0 &.:(b&#)) y
)
NB. Möbius transform:
NB. If an = Sum (over factors d of n) of bd
NB. then
NB. bn = Sum (over factors d of n)of mu(n%d) * ad
NB. allmufactors = all factors with non-repeated primes
allmufactors =: ,@>@(*/&.>/)@(<@(1 , */\)/.~)@~.@:q:
Run
x: +/ sumq >: i. 12000 NB. very nearly a spoiler
to get the required answer in about a second.
It could be probably speeded up, at the cost of more
complexity, by gradually building up composite
denominators from all primes < 12000, rather than
factoring all numbers <: 12000.
Mike
On 10/10/2011 8:37 PM, Boyko Bantchev wrote:
> Here is a solution that runs in constant space and is linear in
> the number of fractions that it finds (it actually only computes
> the denominators, one after another from 1/3 to 1/2).
>
> f =: 3 : 0
> i =. 0
> 'a b' =. 3,y-3|>:y
> while. b>2 do.
> 'a b' =. b,a-~b*<.(y+a)%b
> i =.>:i
> end.
> i
> )
> [solution spoiler removed!]
>
> The problem is that it is very slow for 12000: almost 2 min on my
> computer. A recursive rephrasing, such as
>
> N =: 12000
> fr =. [`(>:@[$:({:,{.-~{:*<.@(N&+@{.%{:))@])@.({:@]>2:)
> 0 fr 3,N-3|>:N
>
> should be somewhat faster, but it miserably runs out of stack
> already at N=190 (while I was hoping fr to be treated as tail-
> recursive and execute in constant space.)
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
