>We know (from our brutish numerical experiments) that the answer is 913*993. >Why does that HAVE to be?
>Well we know the answer must be of the form 9a3*9b3 because the first digit >must be maximal and so the last digit must also be a 9. Now the carry to the first digit must be exactly 1 (not 0 or >1) Ie 90000 <= (10000*9*(a+b))+(1000*a*b)+9 190000 > (10000*9*(a+b))+(1000*a*b)+9 assume a<=b let b be maximal (9) 90000 <= (10000*9*(a+9))+(1000*a*9)+9 10 000 <= (10000*(a+9))+(1000*a)+1 so a must be at least 1. assume 2 for a and b minimal, ie 2. Then 190000 > (10000*9*(2+2))+(1000*2*2)+9 190000 > (360000)+(4000)+9 false, so a=1 and b=9 ie 913*993 greg ~krsnadas.org -- from: 'Pascal Jasmin' via Programming <[email protected]> to: "[email protected]" <[email protected]> date: 8 June 2014 10:10 subject: Re: [Jprogramming] Project Euler Question 4 a little faster too, timespacex '(-: |.)@("."0@":)"0 break2 \:~ ~. , */~ 100+i.900' 0.0301696 3.56781e7 >a disadvantage is that it returns the full list instead of empty if nothing >found. >Robert, its kind of cheating to just assume that you will find the answer in >specific range timespacex '(-: |.)@("."0@":)"0 break2 \:~ ~. , */~ 900+i.100' 0.00273696 1.58502e6 this will scan all of them, but saving the creation of the whole list booltest=: [: -. [: *./ 0 = , NB. allows if. to return false under more cases >NB. for each item of x, create a small argument list for u lazy =: 2 : (':';'for_i. x do. if. booltest o=. u i v y do. o return. end. end.') 1 2 3 (20&<) break1 lazy * i.20 22 (returns 2 * 11) (100 ([ + *) |.i.9) (-: |.)@": break1 lazy (13 : '\:~ ~. , */~ x + y') i.100 906609 timespacex '(100 ([ + *) |.i.9) (-: |.)@": break1 lazy (13 : ''\:~ ~. , */~ x + y'') i.100' 0.00444736 1.32493e6 -- from: Henry Rich <[email protected]> to: [email protected] date: 8 June 2014 09:31 subject: Re: [Jprogramming] Project Euler Question 4 Tacit variant: break2=:1 :'(": 13!:8 (15"_))^:u"u :: (LF taketo }.@(13!:12)@(''''"_) )' (-: |.)@("."0@":)"0 break2 \:~ ~. , */~ 100+i.900 -- from: robert therriault <[email protected]> to: [email protected] date: 8 June 2014 09:31 subject: Re: [Jprogramming] Project Euler Question 4 >Using Roger's method of replacing 100 + i. 900 with 900 + i. 100 I see even >better results and because of the nature to the algorithm even better in >chunks of 50 (especially space). timespacex ' >./ (#~ (-: |.)@":"0) , */~ 100+i. 900' 0.48508 9.46483e6 timespacex '(-: |.)@": break1 \:~ ~. , */~ 100+i.900' 0.0358972 1.78367e7 timespacex ' >./ (#~ (-: |.)@":"0) , */~ 900+i. 100' 0.00559906 151936 timespacex '(-: |.)@": break1 \:~ ~. , */~ 900+i.100' 0.00599915 790144 timespacex ' >./ (#~ (-: |.)@":"0) , */~ 950+i. 50' 0.00145386 40832 20 * 0.00145386 40832 NB. Approx. time and space if you did 100 to 999 exhaustively. Could be faster if you started from the 950 - 999 and worked your way down, stopping at the first hit. 0.0290772 816640 Cheers, bob -- from: Jon Hough <[email protected]> to: "[email protected]" <[email protected]> date: 8 June 2014 09:09 subject: Re: [Jprogramming] Project Euler Question 4 >"A different and perhaps less brutish method is to start with >6-digitpalindromes and see which ones have two 3-digits factors." >I tried that first, but didn't get very far. It turns out to be more tricky >than it seems. At least for me. Namely, finding 3-digit factors. That would >require an exhaustive search of all multiplications of all factors. I think I >can get the number of factors of an integer bysigma0 =. */@:(1&+)@:q: >But if there are many prime factors there are a lot of combinations. -- from: 'Pascal Jasmin' via Programming <[email protected]> to: "[email protected]" <[email protected]> date: 8 June 2014 09:05 subject: Re: [Jprogramming] Project Euler Question 4 >an optimization to short circuit on first true, while sorting them in order. break1 =: (1 : 'for_i. y do. if. u i do. i return. end. end.') (-: |.)@": break1 \:~ ~. , */~ 100+i.900 906609 timespacex '(-: |.)@": break1 \:~ ~. , */~ 100+i.900' 0.0350227 3.56737e7 timespacex ' >./ (#~ (-: |.)@":"0) , */~ 100+i. 900' 0.26438 1.78811e7 -- from: Roger Hui <[email protected]> to: Programming forum <[email protected]> date: 8 June 2014 08:10 subject: Re: [Jprogramming] Project Euler Question 4 Or apply the phrase to 900+i.100 instead of to 100+i.900. -- from: Roger Hui <[email protected]> to: Programming forum <[email protected]> date: 8 June 2014 08:07 subject: Re: [Jprogramming] Project Euler Question 4 Slightly shorter if the formatted results are not converted back into numbers: >./ (#~ (-: |.)@("."0@":)"0) , */~ 100+i. 900 906609 >./ (#~ (-: |.)@":"0) , */~ 100+i. 900 906609 >A different and perhaps less brutish method is to start with 6-digit >palindromes and see which ones have two 3-digits factors. -- from: Henry Rich <[email protected]> to: [email protected] date: 8 June 2014 08:00 subject: Re: [Jprogramming] Project Euler Question 4 >Brute force seems right for this problem. You could write your solution as >./ (#~ (-: |.)@("."0@":)"0) , */~ 100+i. 900 Henry Rich -- from: Jon Hough <[email protected]> to: "[email protected]" <[email protected]> date: 8 June 2014 07:46 subject: [Jprogramming] Project Euler Question 4 >I am pretty pleased that I completed Project Euler Q4. Question: >A palindromic number reads the same both ways. The largest palindrome made >from the product of two 2-digit numbers is 9009 = 91 99. Find the largest palindrome made from the product of two 3-digit numbers. https://projecteuler.net/problem=4 My solution: base =. "."0 ": NB. Tests if y value is palindrome. is_palindrome =. (# =)@:(=|.)@:base NB. multiply all 3 digit nums (100 ~ 999) mult =: (* is_palindrome"0) @ (*/) NB. Create list of 3 digit nums. list =. 100+ i.900 (>./)@:, list mult list >Although I'm glad got the answer, I'm wondering if it could be made terser, or >if there is a much terser way to solve it? I went for a brute force approach. >For comparison here is a Haskell answer I found: >maximum[a*b|a<-[100..999],b<-[a..999],reverse(show(a*b))==show(a*b)] Regards. ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
