|
Post by tenochtitlanuk on Jun 22, 2018 6:01:17 GMT -5
Browsing through Rosetta Code I found- ' Rosetta Code- Largest number divisible by its digits
' Find the largest base 10 integer whose digits are all different, ' and evenly/exactly divisible by each of its individual digits. ' ( Number must not include zero since division by zero is prohibited.)
' For example: 135 is evenly divisible by 1, 3 and 5.
I lashed up quick code late last evening ( no GUI needed here) and set it going. Then saw it was going to take ages. It in fact took near 12 hours!
Thinking more clearly I realised I'd missed various optimisations. DON'T read all the examples on RC- try to solve it yourself! Twelve hours SHOULD be easy to beat!
Don't post code, only time-to-solution. Then fastest person can post their code in say a couple of weeks!
|
|
|
Post by tsh73 on Jun 22, 2018 9:01:34 GMT -5
I've got right number in 37 minutes (and I exhausted other options - so it's really largest one.) ("right" checked on printed Rosetta code, afterwards)
EDIT after some thinking - I did not actually tried all above numbers So while I got right one, my program didn't prove there is no bigger one ;( My guess that it'll take 10x more. Probably try that tonight
err ... it died with Virtual machine stack overflow then run overnight. No error log. EDIT there is error log (in source folder) - but it contains error name, error number (something like 30005) and timestamp. That's all. So now I know program run just over 6 hours then crashed (compared with source program timestamp). Interesting thing that "10x more" from 37 minutes amounts to just about 6 hours. (in the wee hours of night I had that idea that 10x from 37 minutes is somewhere around 3 hours. One really should sleep at night. Like, just now) Must be coincidence. Probably have to check loops leaving...
|
|
Jack Kelly
New Member
I see no benefit from anonymity.
Posts: 8
|
Post by Jack Kelly on Jun 28, 2018 21:35:58 GMT -5
We don't have to test ANY 8 or 9 digit integers, because I propose a new mathematical theorem which states, "No integer with more than seven unique, non-zero digits can be evenly divisible by each of its digits." This will be called the "Anatoly and Jack Postulate." Now all I have to do is prove it!
The proof has something to do with the mutual exclusivity of 4 and 5. This is based on the following observations:
* For ALL integers, NONE that satisfy the criteria contain BOTH a 4 and a 5.
* For integers four or more digits in length, none that satisfy the criteria contain a 5.
* For integers seven digits in length, none that satisfy the criteria contain EITHER a 4 or a 5.
The conclusion from these observations is that ANY eight or nine digit integer with all unique non-zero digits, MUST contain a 4 or a 5, and therefore CANNOT meet the criterion of even digit divisibity.
Therefore we need only to examine the integers from 1 to 9,999,999 (or 9,876,543 if you want to save a few seconds)to find the largest one which satisfies the three criteria -- which my program can do between 12 minutes and 2 minutes, depending on the software, hardware, and operating system environment.
But WHY does 4 and 5 behave in such a way???
|
|
|
Post by tenochtitlanuk on Jun 29, 2018 2:07:28 GMT -5
Good to see you looking at this one, Jack. Have you now looked at the Rosetta Code link? The Perl example shows the best-explained optimisation, and very fast result... Moral- and reason for my posting- is that we should try always to analyse a programming task carefully before and durung coding- and be prepared to think laterally and even start again! The sledge hammer /brute force that computers allow is not always optimal!
|
|
|
Post by tsh73 on Jun 29, 2018 8:14:59 GMT -5
I made my brute-force hammer work in LB Counting for n = 987654321 to 1 step -1 getting digits with Int and MOD It took 5:32:0 ( 5 and a half HOURS) on my working computer (just quietly used 25% of CPU as I rattle with my chores). Previous version had lines like if j mod 100000=0 then print "."; if j mod 6000000=0 then print "(";n;")"
but thinking now - pasting that into 987654321 -length loop was not very bright idea I had a peek at Rosetta code. First explanation (C version) makes me think it will be 20x faster. So I just will try it. EDIT: really, 20x faster. 0:15:5 Will look to Perl after that. EDIT:
very impressive analysis. But really, after proving it's 7 digit number, it world be found very fast by checking numbers one-by-one down - number searched is at very top of 7-digit numbers .
EDIT:
Jack, they beat us with proving your theorem. They were here first! ;(
|
|
|
Post by bluatigro on Jul 24, 2018 1:46:08 GMT -5
i tryed somthing else
i think i made a mistake some were but you get the point i think
it did it in a time of sec in place of minitutes
q$ = "1236789"
for n = 0 to 2 ^ 6 product = 1 for m = 1 to 7 if n and 2 ^ ( m - 1 ) then product = product * val( mid$( q$ , m , 1 ) ) end if next m p$ = str$( product ) fl = 1 for m = 1 to 7 if n and 2 ^ ( m - 1 ) then if instr( p$ , str$( m ) ) = 0 then fl = 0 end if next m if fl then print product next n print "[ game over ]"
|
|
|
Post by bluatigro on Jul 24, 2018 2:11:08 GMT -5
update : eventual typo's removed other results
but not what i wanted
global cyfer$ cyfer$ = "1236789"
for n = 1 to 2 ^ 6 p = 1 for m = 1 to 7 if n and too( m ) then p = p * val( c$( m ) ) end if next m p$ = str$( p ) fl = 1 for m = 1 to 7 if n and too( m ) then if instr( p$ , c$( m ) ) = 0 then fl = 0 end if next m if fl then print p next n print "[ game over ]" end function too( x ) too = 2 ^ ( x - 1 ) end function function c$( x ) c$ = mid$( cyfer$ , x , 1 ) end function
|
|