TheSwamp
Code Red => AutoLISP (Vanilla / Visual) => Topic started by: highflyingbird on January 13, 2012, 09:33:42 AM
-
If a number is composed entirely of 1's? -> 111...1,
How many 1's at least can compose a number ,which can be divided exactly by 2011?
-
Brute force method:
(defun Smallest1 (n / d)
(setq d 1.)
(while (and (not (equal (rem d n) 0. 1.e-16)) (< d 1.797693134862315e308))
(setq d (+ (* d 10.) 1.))
)
d
)Result:_$ (Smallest1 2011)
1.11111e+233I don't think it's the correct one though: 233 - 1's. But it's as close as AutoLisp is going to get to it using just its internal data structures. You'd probably get a better result if you could use BigInts and run it for several days.
-
Brute force method:(defun Smallest1 (n / d)
(setq d 1.)
(while (and (not (equal (rem d n) 0. 1.e-16)) (< d 1.797693134862315e308))
(setq d (+ (* d 10.) 1.))
)
d
)Result:_$ (Smallest1 2011)
1.11111e+233I don't think it's the correct one though: 233 - 1's. But it's as close as AutoLisp is going to get to it using just its internal data structures. You'd probably get a better result if you could use BigInts and run it for several days.
No,it's not the exactly answer.Thank you anyway.
-
So you are looking for the smallest multiple of 2011 composed entirely of 1's?
-
This is my answer.
-
Numbers of the form 1, 11, 111 can be expressed as: (1/9)*(10n-1)
So you are looking for the smallest 'n' such that (1/18099)*(10n-1) = integer?
-
Lee,thank you. I'm sorry for my bad grammar and expression.
-
This is my answer.
Very clever HighflyingBird - I really like your method of removing the multiples of '111...1' by way of 'rem' before multiplying the result so as not to hit the numerical limit for doubles. My naiive method would have been similar to Irneb's.
-
my way:
)
x
(rem (+ (* x
10000) 1111) 2011) )
)
)
_$ (BenchMark '((test1) (test2) (test3)))
Benchmarking ..............Elapsed milliseconds / relative speed for 2048 iteration(s):
(TEST3).....1062 / 4.81 <fastest>
(TEST1).....2781 / 1.84
(TEST2).....5109 / 1.00 <slowest>
_$
-
:-o
-
:)
This is my solution by Lisp
and this is by Python, Brute force is adopted. Python support big num operation, and the speed is acceptable.
sum=0
for i in range(0,2000):
sum=sum*10+1
if(sum%2011==0):
print (i+1)
-
and this is by Python, Brute force is adopted. Python support big num operation, and the speed is acceptable.
It would have been possible to use BigNum in CLisp / Scheme as well, but AutoLisp is restricted to 32bit integers :ugly: ... thanks ADesk! :realmad:
But HyflyingBird & Evgeniy's workaround is truly awesome! Glad there is a way!