Cons Car

[teebee]

Using bit operations the solution can be computed by the following expression:

Code: Select all

(n & ~highest_one_bit(n)) << 1

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).

[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.

[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

[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.

[outsider]

I found this Algo:

Code: Select all

(x-((int) log2(x)))*2

it means the same, but without bitoperations

[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

[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)

[uws8505]

Am I the only one who installed a Scheme interpreter?

[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.

[nuggerator]

I found this Algo:

Code: Select all

(x-((int) log2(x)))*2

it means the same, but without bitoperations

Same idea, but as Maxima expression:

Code: Select all

(x-2^truncate(log(x)/log(2)))*2

[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)