Page 1 of 1
Cons Car
Posted: Sun Feb 08, 2009 11:02 am
by teebee
Using bit operations the solution can be computed by the following expression:
where highest_one_bit(n) is the (binary) value with a single one-bit in the position of the highest-order ("leftmost") one-bit in n (and clearly n = 123456789).
Posted: Sun Feb 08, 2009 9:29 pm
by gfoot
Interesting... I rewrote it in Python and found a way to express the effect it had on sequences, which depended a little on whether the sequence was even or odd in length. But that one-liner is obviously even simpler.
Posted: Wed Mar 25, 2009 5:05 pm
by megabreit
After finding out what this lisp bracket thingy actually does I decided to write a perl version and simply start it.
Being lazy I did not recognize, that the list will grow really big. I managed to kill the program before my system crashed...
There are 2 ways to solve this dilemma:
1) Think of a better algorithm.
2) Get a bigger machine.
I chose 2) and found out, that 8GB of memory (on a 64-bit system with a 64-bit perl and adequate kernel configuration) is enough to run this challenge. I never wrote a perl script which really used 8GB of memory... until today.
I was on the way gfoot took, but could not resist using the box... just because it was there
Posted: Thu Apr 23, 2009 3:22 pm
by Karian
It took me a while to analise the problem so that I understood what was really asked. I know it is based on an existing riddle. I tried to search the web, but couldn't find the riddle (or the solution).
Then I remembered this question was actually asked to me in a job interview. Although I didn't do well that time, I remembered the way of working, solved it for values up to 12, extracted teebee's formula and solved it.
Posted: Sun Sep 06, 2009 5:19 am
by outsider
I found this Algo:
it means the same, but without bitoperations
Posted: Fri Jun 18, 2010 2:04 pm
by jonik555
After long tries with cLISP I finally completed the script that did this for first 30
ns. Then I realized that every power of two is zero and completed it with google calc...
nice one
Posted: Sat Jul 16, 2011 8:09 pm
by moose
I don't understand lisp, but I could manage to get the series. Then I build a python-script to create the same serie:
Code: Select all
def f(end):
i = 0
elementsOutput = 0
elementsOutputCounter = 0
act = 0
while i < end:
elementsOutputCounter = 0
while elementsOutputCounter < elementsOutput:
i += 1
act += 2
elementsOutputCounter += 1
if i == end: return act
elementsOutput = elementsOutput * 2 + 1
i += 1
act = 0
if i == end: return act
return act
def schemeFunction(i):
return f(i-1)
print schemeFunction(123456789)
Posted: Sun Jul 17, 2011 4:17 pm
by uws8505
Am I the only one who installed a Scheme interpreter?
Posted: Wed Nov 16, 2011 8:10 pm
by IIMOG
No, you're not. I also installed the Scheme interpreter and calculated the first 10 numbers, then I calculated
(* 2 (- 123456789 (* 1024 1024 64))) and got the answer. Okay I had to try a bit, before I found what the highest power of two, lower than 123456789 is.
Posted: Thu Mar 28, 2013 3:09 pm
by nuggerator
outsider wrote:I found this Algo:
it means the same, but without bitoperations
Same idea, but as Maxima expression:
Posted: Sat May 23, 2015 10:53 am
by Hippo
After reading basics of scheme, I have optimised the code to the following:
(define (pow2 n)
(do ((i 1 (* 2 i))) ((>= i n) i))
)
(define (f n)
(- (* 2 n) (pow2 n))
)
(display (f 123456789))
what gave correct answer.
(OK i did it in scheme to compare the results easily to be sure the optimised version works well)