Topic: --{challenge}--How many 1's at least?

[highflyingbird]

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?

[irneb]

Brute force method:

Code: [Select]

(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:

Code: [Select]

_$ (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.

[highflyingbird]

Brute force method:

Code: [Select]

(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:

Code: [Select]

_$ (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.

[Lee Mac]

So you are looking for the smallest multiple of 2011 composed entirely of 1's?

[highflyingbird]

This is my answer.

[Lee Mac]

Numbers of the form 1, 11, 111 can be expressed as: (1/9)*(10ⁿ-1)

So you are looking for the smallest 'n' such that (1/18099)*(10ⁿ-1) = integer?

[highflyingbird]

Lee,thank you.  I'm sorry for my bad grammar and expression.

[Lee Mac]

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.

[ElpanovEvgeniy]

my way:

Code - Auto/Visual Lisp: [Select]

1. (defun test3 (/ I X)
2.   (setq i 5
3.         x (rem 11111 2011)
4.   )
5.   (while (not (member x '(203 20 201 0)))
6.     (setq i (+ i 4)
7.           x (rem (+ (* x 10000) 1111) 2011)
8.     )
9.   )
10.   (+ i (vl-position x '(0 201 20 203)))
11. )

Code: [Select]

_$ (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>
_$ 

[Lee Mac]

 

[qjchen]

This is my solution by Lisp

Code - Auto/Visual Lisp: [Select]

1. ;;by qjchen
2. (defun c:test (/ i d)
3.   (setq i 1 d 1)
4.   (while (not (zerop d))
5.     (if (zerop (setq d (rem (+ (* 10 d) 1) 2011))) (princ (1+ i)) (setq i (1+ i)))
6.   )
7.   (princ)
8. )
9.  

and this is by Python, Brute force is adopted. Python support big num operation, and the speed is acceptable.

Code - Python: [Select]

1. sum=0
2. for i in range(0,2000):
3.     sum=sum*10+1
4.     if(sum%2011==0):
5.         print (i+1)
6.  

[irneb]

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!