There is a couple of reasons it fails... First the simplest version uses just
one multiple to apply d to. In the case of S(x,10), that number is 6. It
relies on the hopeful conjecture that multiples of 6 will have more factors
than non multiples, and there is at least one multiple in every range of 10.
This is a false conjecture, but it remains somewhat practical. The approach
generates hops, and tries to determine M() without calculating it between those
hops.
It fails in the case of 90 S 10, because d 80= 10 and provides a higher number
for M for 2 numbers than the surrounding multiples of 6.
+/ 81{. 0 -.~ , 2 ({:@{. #~ [: -~/ {."1)\ ( 0 4) , ( 2 (([: {: {:"1) ,.~
( 0 10 -~ {."1) {~ [: ( <:/ ) {:"1)\ ]) |:@:( ,: d) 6* >: i.16
754
+/ 90 (>./\ d@>:@i.)~/ 10
758
the boxes approach is just a quick patch to fix by considering independently 6
and 8 multiples, and merging the results, the correct answer is obtained for 90
S 10. Instead of the boxed approach, manipulating the list that d will be
applied to include missing key factors would be both faster and cleaner, and
allows * to generate sum instead of #
The key to the approach, is to obtain S, from this following small table:
( 0 4) , ( 2 (([: {: {:"1) ,.~ ( 0 10 -~ {."1) {~ [: ( <:/ ) {:"1)\ ])
|:@:( ,: d) 6* >: i.16
0 4
2 6
8 6
14 8
20 8
26 9
36 8
38 10
48 8
50 12
60 8
62 12
72 8
74 12
80 12
86 12
The right answer could be derived if the 72 8 entry was replaced with 72 10
(reflecting d 80)
There is another unknown bug in my approach in that I end up overestimating
somehow 1000 S 10 by adding boxes, when the intent was to prevent
underestimating.
2e6 +/@:(>./\ d@>:@i.)~/ 100000
448758208 Takes over 10 seconds on my computer
but this is instant:
+/ > 2({:@{.*[:-~/{."1)\each (<0 128),each(10({.@{.,[:(>./){:"1)\])each
|:@:(,:d)each <( ] * [: >: [: i. 2e6<.@% ]) 9240
446883360
Though it needs work on the end range, which could be done by inserting the
step size (1e5) into the d build table.
----- Original Message -----
From: Mike Day <[email protected]>
To: [email protected]
Cc:
Sent: Thursday, October 23, 2014 3:07 PM
Subject: Re: [Jprogramming] An easy Euler Project one (485)
This might help see where it goes astray:
(~.,:#/.~)/:~ 10 >./\ dsieve 1000
4 6 8 9 10 12 14 15 16 18 20 21 24 27 28 30 32
2 12 24 12 16 174 16 20 245 158 102 10 160 10 10 10 10
+/ 10 >./\ dsieve 1000
17176
(~.,:#/.~)/:~991{.{. >./ ,:&> 0 -.~ [...] each boxes
4 6 8 9 10 12 14 15 16 18 20 21 24 27 28 30 32
2 12 22 12 18 174 14 20 247 158 102 10 160 10 10 10 10
NB. despite using fixed width font I've had to hand-align these!
I had thought you should be using
<.1000%21 14 10 15 125 27 8 6
for the length of each a.p., ie to get >:i.47, >:i.71 etc, but that
doesn't work either, providing only 990 elements, and sum 17168 .
I can't quite get what you're doing here. (I can talk!) I see that
21* will hoover up all numbers with 3 & 7 as factors, but its list
will include numbers also generated by 14* and 15* etc.
FWIW, 48390900720 is about 5% away from the correct answer.
Got to go out now, so that's it for the time being.
Mike
On 24/10/2014 03:17, 'Pascal Jasmin' via Programming wrote:
> got distracted for the day with this approach:
>
> boxes =. (21* >:i.48) ;(14* >:i.77) ;(10* >:i.100) ;(15* >:i.70) ;(125*
> >:i.8) ; (27* >:i.36) ; (8* >:i.127) ; 6* >: i.168
>
> +/ 991 {.{. >./ ,:&> 0 -.~ each , each 2 ({:@{. #~ [: -~/ {."1)\ each (<
> 0 4) , each ( 2 (([: {: {:"1) ,.~ ( 0 10 -~ {."1) {~ [: ( <:/ ) {:"1)\ ])
> each|:@:( ,: d) each boxes
>
> 17184
>
> its the wrong answer, but close :(
>
> but it can provide a super quick estimate of 1e8, 1e5
>
> +/ 0 -.~ , &> 2 ({:@{. * [: -~/ {."1)\ each (< (, d) 1e8 -1e5) ,~ each (<
> 0 128) , each ( 10 ( {.@{. , [: ( >./ ) {:"1)\ ]) each |:@:( ,: d) each <
> 9240* >: i. <: <: 1e8 <.@% 9240
> 48390900720
>
> timespacex '+/ 0 -.~ , &> 2 ({:@{. * [: -~/ {."1)\ each (< 0 128) ,
> each ( 10 ( {.@{. , [: ( >./ ) {:"1)\ ]) each |:@:( ,: d) each < 9240* >: i.
> 1e8 >.@% 9240'
> 0.0413071 1.85434e6
>
>
>
>
> ----- Original Message -----
> From: 'Pascal Jasmin' via Programming <[email protected]>
> To: "[email protected]" <[email protected]>
> Cc:
> Sent: Tuesday, October 21, 2014 7:15 PM
> Subject: Re: [Jprogramming] An easy Euler Project one (485)
>
> a complication with the approach is:
>
> */ 2 2 2 3 3 5 5 7 11
> 138600
>
> d */ 2 2 2 3 3 5 5 7 11
> 144
>
> and so for the ranges starting at 38600 to 63320 there is a greater maximum,
> and it also appears that for some multiples of 138600, the number of divisors
> exceeds (for part of the range) of multiples of 83160
>
> a number that simplifies the process is:
>
> */ 2 2 2 3 5 7 11
> 9240
>
> as it allows needing to examine with d only multiples of it.
>
>
>
> ----- Original Message -----
> From: Raul Miller <[email protected]>
> To: Programming forum <[email protected]>
> Cc:
> Sent: Tuesday, October 21, 2014 6:41 PM
> Subject: Re: [Jprogramming] An easy Euler Project one (485)
>
> See also http://oeis.org/A002182
>
> Also Roger Hui's point about a sieve is probably a good one since this
> problem only needs you to consider prime factors less than 10000. Still,
> those 1229 prime factors multiplied by the 1e8 limit means we would need
> something on the order of several terabytes of memory for intermediate
> results if we were to store the entire sieve in the obvious way. So some
> extra work would be needed, and I'm not sure how that would pan out.
>
---
This email is free from viruses and malware because avast! Antivirus protection
is active.
http://www.avast.com
-----
No virus found in this message.
Checked by AVG - www.avg.com
Version: 2014.0.4765 / Virus Database: 4040/8441 - Release Date: 10/23/14
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
