### What is the smallest positive integer with no google hits?

Posted:

**Sat Feb 07, 2009 8:44 pm UTC**So, what would you guess is the smallest positive integer with no google hits?

Forums for the webcomic xkcd.com

http://fora.xkcd.com/

Page **1** of **1**

Posted: **Sat Feb 07, 2009 8:44 pm UTC**

So, what would you guess is the smallest positive integer with no google hits?

Posted: **Sat Feb 07, 2009 8:53 pm UTC**

Surely testing each would be the best way to find out?

I daresay somebody can write a script to do it for us.

I daresay somebody can write a script to do it for us.

Posted: **Sat Feb 07, 2009 9:13 pm UTC**

Here's an upper limit: 387462325

I just slammed my keyboard and nothing showed up.

I just slammed my keyboard and nothing showed up.

Posted: **Sat Feb 07, 2009 9:17 pm UTC**

Of course, that won't be true for long, now that it's been posted here.

Posted: **Sat Feb 07, 2009 9:34 pm UTC**

If this thread were in faid, that wouldn't happen.

Posted: **Sat Feb 07, 2009 10:48 pm UTC**

It probably should be in faid, since this isn't math. Just because it uses numbers, doesn't mean it's math.

Posted: **Sat Feb 07, 2009 10:48 pm UTC**

I think a more interesting question (well, how I originally interpreted this one, anyway) would be

What is the smallest positive integer n such that no google search returns n hits?

What is the smallest positive integer n such that no google search returns n hits?

Posted: **Sat Feb 07, 2009 10:52 pm UTC**

Well, the problem with that question is that Google starts approximating when the numbers get large.

Posted: **Sat Feb 07, 2009 10:53 pm UTC**

I wasn't sure about the forum placement, but then I read somewhere else about someone estimating the answer using a smattering of probability theory. http://godplaysdice.blogspot.com/2008/09/first-number-not-in-google.html thinks that the answer has to be in the high eight digits.

Posted: **Sun Feb 08, 2009 8:33 pm UTC**

skeptical scientist wrote:Well, the problem with that question is that Google starts approximating when the numbers get large.

The bigger problem is that the number of hits is itself not a constant; it depends both on the current state of the internet and on your proximity to certain local servers (or something along those lines); I've definitely seen the Google hits for the same search vary by as much as 100% within the same day on different computers.

Posted: **Mon Feb 09, 2009 12:15 am UTC**

I'd suggest Graham's number. And rule any number larger to be useless, and any number less to be used.

(I might have totally missed the meaning of a "Graham's number" there. Just trying to say you could take the largest useful number, and not expect to get any returns for anything bigger.)

(I might have totally missed the meaning of a "Graham's number" there. Just trying to say you could take the largest useful number, and not expect to get any returns for anything bigger.)

Posted: **Mon Feb 09, 2009 1:16 am UTC**

Graham's number is an actual well-defined number, but the fact that its decimal representation can't exactly be plugged into Google makes that not quite in the spirit of the question.

Posted: **Mon Feb 09, 2009 1:26 am UTC**

On the other hand, Graham's number definitely does have google hits, you just can't get them by typing a sequence of digits in. Also, being as there are *way* less bits of data than that in the universe, it's not possible for everything under it to get a hit.

Even ignoring actual cases of 9-digit numbers that return no hits (there was at least one before this thread got found by Google), we can compute a certain upper bound for the number we're looking for:

Let's be generous and suppose there are 10^24 bytes of data searched by Google. (This is rather excessive, by several orders of magnitude, as it would mean more than a hundred TB for every human being on Earth.) Then since large numbers take way more than one byte to store, we can be 100% certain that the smallest integer with no Google hits is smaller than 10^24, since there is simply no physically possible way for all of those smaller numbers to turn up results.

Even ignoring actual cases of 9-digit numbers that return no hits (there was at least one before this thread got found by Google), we can compute a certain upper bound for the number we're looking for:

Let's be generous and suppose there are 10^24 bytes of data searched by Google. (This is rather excessive, by several orders of magnitude, as it would mean more than a hundred TB for every human being on Earth.) Then since large numbers take way more than one byte to store, we can be 100% certain that the smallest integer with no Google hits is smaller than 10^24, since there is simply no physically possible way for all of those smaller numbers to turn up results.

Posted: **Mon Feb 09, 2009 4:19 am UTC**

gmalivuk wrote:(This is rather excessive, by several orders of magnitude, as it would mean more than a hundred TB for every human being on Earth.)

Clearly you fail to grasp the sheer scale of the porn industry.

Posted: **Mon Feb 09, 2009 4:29 am UTC**

Haha, fair. Also, since the earlier number has probably now become one Google gives results for, let me just say that 35375831*7*2 also, as of this post, has no results.

Posted: **Mon Feb 09, 2009 5:56 am UTC**

I was wondering, what would be a fast algorithm to test this? Assume a google search is more time consuming than simple checks of a number's properties. I was thinking that the following would have to be incorporated:

A lower bound should be used. It's unlikely that any number below around 1 million has no entries, so that's somewhere to start.

OEIS sequences will return any small number that has interesting properties. Furthermore, especially interesting properties will be hit somewhere else. So a bare minimum is skipping over prime numbers. Realistically, we should also skip things like digits of pi, any binary expression, and any number which is significant in computer science. Unfortunately, eliminating these is only a small fraction of all the numbers we need to get rid of.

Any number that can be expressed concisely is out. So eliminate all powers of small integers. Also, powers of 10 should have regions eliminated around them, as people often type 100000002 or 9999999. Numbers that have a lot of prime factors are also eliminated.

Unfortunately, it feels like this style of algorithm is not useful. Applying so many tests becomes slower than just running a google search at some point. So this question is essentially related to the question "what makes a number interesting (or not) to someone?" It's something that seems impossible to quantify, and thus is probably very hard to answer mathematically (and it changes over time).

to the OP: do you know the answer, or are you trying to find an efficient way to find it?

edit: I found 911266235 which has no hits. Phone numbers make it hard to hit things under 10 digits, so starting with 911 helped.

A lower bound should be used. It's unlikely that any number below around 1 million has no entries, so that's somewhere to start.

OEIS sequences will return any small number that has interesting properties. Furthermore, especially interesting properties will be hit somewhere else. So a bare minimum is skipping over prime numbers. Realistically, we should also skip things like digits of pi, any binary expression, and any number which is significant in computer science. Unfortunately, eliminating these is only a small fraction of all the numbers we need to get rid of.

Any number that can be expressed concisely is out. So eliminate all powers of small integers. Also, powers of 10 should have regions eliminated around them, as people often type 100000002 or 9999999. Numbers that have a lot of prime factors are also eliminated.

Unfortunately, it feels like this style of algorithm is not useful. Applying so many tests becomes slower than just running a google search at some point. So this question is essentially related to the question "what makes a number interesting (or not) to someone?" It's something that seems impossible to quantify, and thus is probably very hard to answer mathematically (and it changes over time).

to the OP: do you know the answer, or are you trying to find an efficient way to find it?

edit: I found 911266235 which has no hits. Phone numbers make it hard to hit things under 10 digits, so starting with 911 helped.

Posted: **Mon Feb 09, 2009 7:26 am UTC**

I know neither the answer nor an efficient way to find it. Someone just asked me what I would guess (my initial guess was something around 100000, way too low). I suspect it might be relatively quick for someone internal to Google to find out.

Posted: **Mon Feb 09, 2009 7:39 am UTC**

Isn't this just an exercise in induction, because once the answer is found, it will just be posted and then no longer be true? I mean it's a fun thing to look for, but I guess the only way to do this and not destroy the meaning would be to refer to the result by its prime factorization, like gmalivuk did with his upper bound. If the number is prime... that won't work either, but I think a prime would be much more likely to come up in some list of primes, so it probably wouldn't be a problem.

Posted: **Mon Feb 09, 2009 8:04 am UTC**

I can pretty much guarantee that the lowest such number is not prime. Lists of primes online go past the lowest upper bounds that have been posted. And I was sort of excluding hits due to this thread, but regardless, that wouldn't make it incorrect when it was posted, just as soon as google updated their index.

Posted: **Mon Feb 09, 2009 8:15 am UTC**

Hmm, I have a smaller number (even smaller than the possibly disqualified number) that returns no hits:

74123129*5

Beat that! (I found it by doing a simple hill-climbing algorithm by hand, maybe someone should try coding up an actual AI to search for solutions )

Edit: a second try at hill-climbing gave me the local minimum 9592578*10, with only 9 hits. Can anyone find an eight digit number with fewer hits?

Edit 2: ok, actually, I just realized I never tried adding digits in front of that last guy, so now I have a new record for 0 hits:

2243*131933

74123129*5

Beat that! (I found it by doing a simple hill-climbing algorithm by hand, maybe someone should try coding up an actual AI to search for solutions )

Edit: a second try at hill-climbing gave me the local minimum 9592578*10, with only 9 hits. Can anyone find an eight digit number with fewer hits?

Edit 2: ok, actually, I just realized I never tried adding digits in front of that last guy, so now I have a new record for 0 hits:

2243*131933

Posted: **Mon Feb 09, 2009 2:16 pm UTC**

qinwamascot wrote:Unfortunately, it feels like this style of algorithm is not useful. Applying so many tests becomes slower than just running a google search at some point. So this question is essentially related to the question "what makes a number interesting (or not) to someone?" It's something that seems impossible to quantify, and thus is probably very hard to answer mathematically (and it changes over time).

You might be going about it too mathematically. It occurs to me that between 4 and 10ish digits the common numbers you're going to find are things like ID numbers, social security numbers, Amazon order numbers... there are a variety of reasons to assign numbers with digits in this range, so I can't help but think that searching itself is the most efficient algorithm available.

Posted: **Mon Feb 09, 2009 9:26 pm UTC**

Smallest yet - 7349*3019:)

EDIT: just beat myself - try 79*34629

That's only 7 digits.

I don't think there are any six digit numbers not indexed, as it only takes a megabyte to store each and everyone of them. Kudos to anyone who can find a result with less then 5 results, though.

EDIT: just beat myself - try 79*34629

That's only 7 digits.

I don't think there are any six digit numbers not indexed, as it only takes a megabyte to store each and everyone of them. Kudos to anyone who can find a result with less then 5 results, though.

Posted: **Mon Feb 09, 2009 9:58 pm UTC**

Compintuit wrote:EDIT: just beat myself - try 79*34629

That's only 7 digits.

Is that supposed to be multiplication, or an extra star to foil the Google bot? Either interpretation returns multiple hits.

Posted: **Mon Feb 09, 2009 9:59 pm UTC**

Compintuit wrote:EDIT: just beat myself - try 79*34629

That's only 7 digits.

I get ~1660 hits for that.

Posted: **Mon Feb 09, 2009 10:10 pm UTC**

I get 1760 for that.

As a side note, should the numbers be typed with commas to indicate powers of 1000? Like when you write 1,231,415? This seems to be less common online, but is technically probably more correct.

As a side note, should the numbers be typed with commas to indicate powers of 1000? Like when you write 1,231,415? This seems to be less common online, but is technically probably more correct.

Posted: **Mon Feb 09, 2009 10:18 pm UTC**

Token wrote:Compintuit wrote:EDIT: just beat myself - try 79*34629

That's only 7 digits.

Is that supposed to be multiplication, or an extra star to foil the Google bot? Either interpretation returns multiple hits.

It didn't really make any sense, but this guy added stars, so I figured operations were acceptable - is that not true? Oh, and you are searching for the number with quotes, right? Otherwise the bot approximates, and finds numbers close to you.

notzeb wrote:Hmm, I have a smaller number (even smaller than the possibly disqualified number) that returns no hits:

74123129*5

Beat that! (I found it by doing a simple hill-climbing algorithm by hand, maybe someone should try coding up an actual AI to search for solutions )

Edit: a second try at hill-climbing gave me the local minimum 9592578*10, with only 9 hits. Can anyone find an eight digit number with fewer hits?

Edit 2: ok, actually, I just realized I never tried adding digits in front of that last guy, so now I have a new record for 0 hits:

2243*131933

Posted: **Mon Feb 09, 2009 10:34 pm UTC**

No, the stars are for multiplication. We're factoring numbers so they don't show up in this thread, because then Google will start showing hits for those numbers when it runs through this thread again.

Posted: **Tue Feb 10, 2009 12:08 am UTC**

Ahh, makes lots of sense now.

Not the highest, but still:

Me thinks a pic is a nice easier way to hide things

Site is http://www.hidetext.net

Ahh, I just found it!!!

It's got the maximum amount of characters a search will allow, but is still 11! Those 1-10 were already used, though.

Do I win, or get kicked out for cheating?

Not the highest, but still:

Me thinks a pic is a nice easier way to hide things

Site is http://www.hidetext.net

Ahh, I just found it!!!

It's got the maximum amount of characters a search will allow, but is still 11! Those 1-10 were already used, though.

Do I win, or get kicked out for cheating?

Posted: **Tue Feb 10, 2009 2:36 am UTC**

Compintuit wrote:Ahh, makes lots of sense now.

Not the highest, but still:

Me thinks a pic is a nice easier way to hide things

Site is http://www.hidetext.net

Ahh, I just found it!!!

It's got the maximum amount of characters a search will allow, but is still 11! Those 1-10 were already used, though.

Do I win, or get kicked out for cheating?

Zero is not a positive integer.

Posted: **Tue Feb 10, 2009 2:51 am UTC**

dean.menezes wrote:Zero is not a positive integer.

Get a bigger screen... that image is "<lots of zeros>11", the end is probably being cut off at your end.

Posted: **Tue Feb 10, 2009 3:05 am UTC**

phlip wrote:dean.menezes wrote:Zero is not a positive integer.

Get a bigger screen... that image is "<lots of zeros>11", the end is probably being cut off at your end.

OK. Yeah. I see it now.

Code: Select all

`#!/bin/sh`

export NUM=1

until wget --user-agent 'Mozilla/4.0 (compatible; MSIE 7.0; Windows NT 6.0)' http://google.com/search?q=$NUM -O - | grep -q 'No standard web pages containing all your search terms were found';

do

echo $NUM

NUM=$(echo $NUM + 1 | bc)

done

echo $NUM

Posted: **Tue Feb 10, 2009 5:02 am UTC**

Appending 0's to the beginning is clearly cheating. The question is what's the smallest integer that gets no hits, not what's the smallest integer that can be represented by a string that gets no hits. The integer 11 does get hits, so it can't be the answer. And anyway, if you're going to do it like that, here's a string that (as of now) also gets none:

000000001.000000000

000000001.000000000

Posted: **Tue Feb 10, 2009 5:23 am UTC**

Right, if we are going to allow non standard representations to count, then we should just go all out and note that "the smallest positive integer with no google hits" currently returns 2 hits, and therefore does not exist...

Posted: **Thu Feb 12, 2009 11:52 am UTC**

each positive integer deserves at least one hit.

wait...

wait...

Posted: **Thu Feb 12, 2009 3:10 pm UTC**

raptor.fortress wrote:each positive integer deserves at least one hit.

wait...

Just wait. Google will make it happen.