Sanding our assholes with 150 grit. Slowly. Lovingly.

Bram Cohen jerks furiously to Fundamental Theorem of Arithmetic

http://bramcohen.livejournal.com/36766.html

The best I can come up with is 30975
Permalink Michael B 
April 3rd, 2007 10:55pm
whenever i see 'Bram' I think of the Dracula guy. those Cohens are sick to name their kids those things ... Sasha, Bram, Leonard.
Permalink Send private email strawberry snowflake 
April 3rd, 2007 11:17pm
Is 30975 a power of 2?
Permalink Mechanical Engineer 
April 3rd, 2007 11:21pm
No, 2 ^ 30975
Permalink Michael B 
April 3rd, 2007 11:36pm
There IS a largest?

Better get back at my calculator...
Permalink Rick Zeng/Tseng 
April 4th, 2007 12:35am
Are you guys writing code for this, or using Mathematica, or do you have some sort of nifty bigint calculator for working on things?

A bigint calculator that ran from the command line would be useful.
Permalink Practical Economist 
April 4th, 2007 12:47am
PE, bc
Permalink Rick Zeng/Tseng 
April 4th, 2007 1:08am
OK, that works. Thanks.
Permalink Practical Economist 
April 4th, 2007 1:17am
And its special ibase and obase metavariables sure are handy!
Permalink Practical Economist 
April 4th, 2007 1:20am
I know theoretical that works. But I don't know whether it's pratical.
Permalink Rick Zeng/Tseng 
April 4th, 2007 1:21am
bc is fucking awesome! man bc for an earful!
Permalink Practical Economist 
April 4th, 2007 1:34am
"What is the exponent of the largest power of two whose base seven representation doesn't contain three zeros in a row?"

Eh? Isn't it unbounded as atated? Or is there something special about septimal arithmetic that says all powers of two must contain three zeroes in a row once the first power of two containing three consecutive zeroes has been encountered? Or am I missing something obvious?
Permalink trollop 
April 4th, 2007 1:36am
There are tons of them that have 000. The trick is which one that doesn't have that is the highest one and how do you know.
Permalink Practical Economist 
April 4th, 2007 1:38am
Ah shit, bc only allows the argument to ^ to be at max 32767.
Permalink Practical Economist 
April 4th, 2007 1:41am
Oh wait, no, it's LONG_MAX. OK.
Permalink Practical Economist 
April 4th, 2007 1:41am
7 is 8 - 1.

It MUST be related somehow ...
Permalink Rick Zeng/Tseng 
April 4th, 2007 1:44am
My analysis shows this base 7 number as the biggest power of 2 without 3 consecutive zeros:

22351661026363652312016405256642433131636423516636114646515462311633552555526000361256340063156043405331143001423434325010264542554612205561616350663651060562414465300120215432251101354263610430656545252213363023663563560041162305111353042006052225055016122115263541266605220464105624004462066624632506243642020063433634433422126635356542402365362014115143102120331415116021434263252220005432612402133525511605246553041621530200400526312626142612440052406132462222323155315232025151232


The previously stated answer of 2^30975 is not correct. It DOES have a run of 000 in it towards the least significant digits:

...32401663165401451330004220614442444141515255025550123561025326323305360023046012030105134255451003102331013142423106536066031244304233241536403365106600442036135044310143042336554303541132045443051411546133562244212056121500165545626353641110232502564211312362206066152301200643004221241501

And we now return you to our regularly scheduled posts where people say "You stopid dumb fuck Practical Economist, you are the most fucked up retarded fuck ass know nothing fascist nazi I have ever seen on any fucking board anywhere, dumbass!"
Permalink Practical Economist 
April 4th, 2007 3:06am
Hm, this board seems to truncate long lines weirdly in my browser.
Permalink Practical Economist 
April 4th, 2007 3:07am
It only truncates from fucking dumbasses' posts.
Permalink Send private email Ward 
April 4th, 2007 3:12am
Exactly!
Permalink Practical Economist 
April 4th, 2007 3:16am
Especially since I can now see that my answer was completely wrong!
Permalink Practical Economist 
April 4th, 2007 3:18am
Well, I can't reply over there because it won't let me post without a LiveJournal account. However, the question is badly and illogically worded. I'd suggest the reason Bram hasn't got any right answers is probably because asking such a dumb question has excluded him from consideration by all the brightest candidates.  It would certainly exclude him from my consideration. Why would I consider an employer who can't write grammatical English or pose a logically solvable problem?

"What is the exponent of the largest power of two whose base seven representation doesn't contain three zeros in a row?"

I think he means to say "What is the largest power of two..." and has somehow got the superfluous and ambiguous "exponent" bit mixed up in there.

Secondly, any "what is the largest..." question can only be solved by a mathematical proof. There is no simple code solution by searching. For any large number you found, there might be an even larger one that matches, and how can you prove it doesn't exist without searching all the way to infinity?

If he meant "what is the *first* power of two..." it would be different, but he didn't say that. Grammatical and logical imprecision again.

A definite no hire.
Permalink Send private email bon vivant 
April 4th, 2007 3:29am
I agree bv. It's dumb question. Asking for the "highest" in this case is silly. Asking for a few examples of numbers that satisfy the criteria would have been a good question.

In this case cohen played himself while trying to be cute.
Permalink $-- 
April 4th, 2007 10:16am
> The previously stated answer of 2^30975 is not correct. It DOES have a run of 000 in it towards the least significant digits.

Not in base 7.
Permalink Michael B 
April 4th, 2007 12:35pm
Obviously I am not the best judge of English usage, but in this case he is explicitly asking for the exponent of the largest power of 2, not the largest power.

It's a precise question.

My first impression is exactly like bon's. How can you calculate the largest? But I'll assume he knows his stuff and I need to find out the right approach.
Permalink Send private email Rick Zeng/Tseng 
April 4th, 2007 1:44pm
Bolton, the sequence of your number I posted with the 000 WAS from the base 7 representation.
Permalink Practical Economist 
April 4th, 2007 2:18pm
Oh, I guess my base 7 conversion is broken.
Permalink Michael B 
April 4th, 2007 5:16pm
he says in the comments that its impossible to know the largest, but just a big number would have done.
Permalink $-- 
April 4th, 2007 5:23pm
Fuck, yeah, how retarded. I implemented it as:

def base7(x):
    return str(x / 7) + str(x % 7)


Changed it to:

def base7(x):
        s = ''
        while 1:
                s = str(x % 7) + s
                if (x / 7) > 0:
                        x /= 7
                else:
                        break
        return s
Permalink Michael B 
April 4th, 2007 5:27pm
Oh ...

That's stupid!
Permalink Send private email Rick Zeng/Tseng 
April 4th, 2007 6:47pm
Well I got the right answer it seems - he invited me in for an interview. I'll probably just stay where I am but it was cool to get the right one. It's NOT a prime number.
Permalink Practical Economist 
April 4th, 2007 10:59pm
Oh yeah if you're doing the whole conversion to base 7 for every damn number you're slowing yourself down quite a bit. O(n)/O(log(n)) or something.

And of course if the digit before the three 0's in a number is a 1, 2 or 3, twice that number will also have three 0's in a row. Quite obvious no? That cuts the work by close to 3/7th, right there.
Permalink Send private email strawberry snowflake 
April 4th, 2007 11:00pm
Well, I gave in and spent a couple of minutes testing it over a coffee break. It seems that powers of 2 in base 7 that *don't* have a string of three consecutive 0's in them get increasingly rare as the numbers get bigger. Definitely, after a while it seems like there won't be any more.

Now I wonder if there is a mathematical proof that there is or isn't a largest such number? That's going to take a whole bunch longer to think about than writing the half-dozen lines of code to investigate the problem.
Permalink Send private email bon vivant 
April 5th, 2007 4:49pm
Currently, there are almost no proofs in this part of mathematics dealing with what sorts of subsequences you might find in a given base of some number without actually looking for them. So, you can spend a few months or years trying to prove it, but you'll probably not get anywhere. You might though. Gotta decide if you want to spend a few years on that problem then.
Permalink Practical Economist 
April 5th, 2007 10:18pm

This topic is archived. No further replies will be accepted.

Other topics: April, 2007 Other topics: April, 2007 Recent topics Recent topics