Monday morning math puzzle

[flexagon]

It's Monday morning, time to re-engage those sluggish little neurons. Here's a cute math problem someone walked into my office with last Friday:

How many numbers N between 1 and 2005, inclusive, can be expressed in the form

floor(x * floor(x)) = N

where x can be any real number?

For those not familiar with "floor", it means take the first integer that's less than or equal to x. So the floor of 2.0 is 2, the floor of 3.5 is 3, the floor of -1.9 is -2. So, to get you started, N is definitely always an integer.

If you think you know the answer and it's been less than 60 seconds, you probably think the answer is "the perfect squares". You are wrong, or rather, your answer is incomplete. Try again. :)

To make this interesting, the first person to respond with the right answer gets to choose between the following prizes: a physical box of cookies mailed to your doorstep (you get to express a preference but I'll pick the cookies), or the right to define an icon which I will use for 10 non-private posts in a row immediately following your posting of that icon in a comment.

Edit: blue has pointed out there's an ambiguity in the problem, so I changed it from '0 to 2005' to '1 to 2005, inclusive'.

Edit: And J has pointed out that I had a REALLY bad typo... + versus *. MOTHERFUCKER! I have no idea how that happened. :( I reread this several times to make sure it was right and... it wasn't. I'm really sorry. Anyone game for trying again? I'll delete all the comments.

Comments

[miyyu.livejournal.com]

Owie! It's been much longer than I remember since I did any kind of higher math, though at least on paper I used to be good at it...

[flexagon]

Sigh, me too... I'm trying to get better again though, since I do like it and I'm surrounded by math-heads at work.

[jg26.livejournal.com]

OK, I did the problem kinda backwards. I wrote a simple little program to loop through the code... here's the code (in IDL)...

PRO FLEXY
prev_val = 0
count = 0
FOR x = DOUBLE(1.0), CEIL(SQRT(2005)), .000001 DO BEGIN
N = FLOOR(x*FLOOR(x))
IF N NE prev_val THEN BEGIN
IF N GT 2005 THEN BREAK
print, x, N
count++
ENDIF
prev_val = N

ENDFOR
print, "TOTAL:", count
END


'count' gives the correct answer... 990. but why?

The pattern is tricky if you're just looking at the values of N... 1, 4, 5, 9, 10, 11, 16, 17, 18, 19... but, if youre looking at the values of x, the pattern becomes obvious... 1, 2, 2.5, 3, 3.3333, 3.6666, 4, 4.25, 4.5, 4.75, 5, 5.2.... get it?

44^2 is the lowest square below 2005... so just sum 1+2+3+4+....+43+44 and you get 990.

[jg26.livejournal.com]

sorry about the lack of indents.

[bluechromis.livejournal.com]

cheater. ;-)

[flexagon]

Holy god, every 0.000001... that really is cheating betrays an initial lack of understanding of the underlying number theory. :)

But you win. Your choice of cookie or humiliating icon!!

[jg26.livejournal.com]

I told you I was cheating... brute force methods to get to the answer.... call it problem solving. "Thinking about it" would've taken too long. ;)

Cookies, please (though it is tempting to get some really raunchy animated icon).

[bluechromis.livejournal.com]

so much for cheaters never prosper. ;-) Cookie stealer. :-D

[flexagon]

But you did think about it afterward and figured out why the answer. What kind of cookies?

change of heart.

[jg26.livejournal.com]

B & I have come up with a great icon we want to create...

mwahhhahhhahhh

Re: change of heart.

[flexagon]

Well? I'm waiting for my dose of humiliation... let's have it. :)

Re: change of heart.

[jg26.livejournal.com]

sorry, I lack the time at the moment to do what I wanted... can I change back to cookies? I like peanut butter, oatmeal, chocolate chip... pretty much anything (only can you make sure their vegetarian, so that b can have some? thanks) ;)

what's precision got to do with it?

[jg26.livejournal.com]

every 0.000001... that really is cheating betrays an initial lack of understanding of the underlying number theory.

why do you say that? If you're gonna go with a brute force method... how better to cover the reals? Plus, for such a limited range, it took less than a minute. Not to mention, I had the program already written for the '+' version of the problem, since analytically I came to the same conclusion as everyone else, and you said it was wrong. So, I never tried to understand it in a number theory sense. Only one character change was necessary.

[bluechromis.livejournal.com]

I was cheated, I say, CHEATED!

every perfect square
plus er...can't write this without symbols very concisely. plus (every number which is an integer x squared plus an integer less than that integer.)

Eg. for 1 the only result is 1
for 2 you get 4 (2^2) AND 5 (2^2 + 1)
for 3 you get 9 (3^2) AND 10 (3^2 + 1) AND 11 (3^2 + 2)
etc. up to 44 which is the highest integer whose square is less than 2005.

so how many that totals =
44
+ 1+2+3+4...+43 = 990

[flexagon]

Nice going. Maybe if J chooses the cookies he will share them with you.

[artana.livejournal.com]

I think we should all get cookies!! Or Blue should, cause she answered it right in the light it was originally presented.;)