### Bram Cohen jerks furiously to Fundamental Theorem of Arithmetic

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.

strawberry snowflake
April 3rd, 2007 11:17pm

Is 30975 a power of 2?

Mechanical Engineer
April 3rd, 2007 11:21pm

No, 2 ^ 30975

Michael B
April 3rd, 2007 11:36pm

There IS a largest?

Better get back at my calculator...

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.

Practical Economist
April 4th, 2007 12:47am

PE, bc

Rick Zeng/Tseng
April 4th, 2007 1:08am

OK, that works. Thanks.

Practical Economist
April 4th, 2007 1:17am

And its special ibase and obase metavariables sure are handy!

Practical Economist
April 4th, 2007 1:20am

I know theoretical that works. But I don't know whether it's pratical.

Rick Zeng/Tseng
April 4th, 2007 1:21am

bc is fucking awesome! man bc for an earful!

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?

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.

Practical Economist
April 4th, 2007 1:38am

Ah shit, bc only allows the argument to ^ to be at max 32767.

Practical Economist
April 4th, 2007 1:41am

Oh wait, no, it's LONG_MAX. OK.

Practical Economist
April 4th, 2007 1:41am

7 is 8 - 1.

It MUST be related somehow ...

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!"

Practical Economist
April 4th, 2007 3:06am

Hm, this board seems to truncate long lines weirdly in my browser.

Practical Economist
April 4th, 2007 3:07am

It only truncates from fucking dumbasses' posts.

Ward
April 4th, 2007 3:12am

Exactly!

Practical Economist
April 4th, 2007 3:16am

Especially since I can now see that my answer was completely wrong!

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.

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.

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

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.

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.

Practical Economist
April 4th, 2007 2:18pm

Oh, I guess my base 7 conversion is broken.

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.

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

Michael B
April 4th, 2007 5:27pm

Oh ...

That's stupid!

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.

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.

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.

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.

Practical Economist
April 5th, 2007 10:18pm