Numbers are, for the most part, made up of other numbers. Prime numbers (2, 3, 7, etc.) are simple, in that they make up themselves — they have no non-trivial factors, and can only be divided by the natural numbers 1 and themselves. Compound numbers, on the other hand, may have entirely different roots.
Some compound numbers, like 6 or 21, are still relatively simple — they are the product of two primes. Other compound numbers, like 144 or 1183, can be divided by squared numbers — 144 can be divided by 4, 9, 16, and 144, and 1183 can be divided by 169 (or 132.) Both of these numbers definitely have factors of the form n2, or (to coin a math pun) “squared roots.”
A collection of squared roots from around the interwebs.
This week’s GeekDad Puzzle of the Week deals with “squared roots,” or more specifically, numbers without any squared roots.
The question: How many of the numbers under 10 million do not have squared roots; that is, how many numbers under 107 cannot be evenly divided by a squared number?
There were two main paths taken by those who responded to come up with an answer: constructive, where answers were built and counts accumulated, and destructive, where people started with all the possibilities and then rules them out for various reasons.
The destructive path was more straightforward, and typically involved code. One brute-force method used was to calculate the prime factorization for each and every number from 1 to 10,000,000, and then examine each for primes with exponents of 2 or greater.
A more elegant path would be to run a modified version of the Sieve of Eratosthenes, where the numbers from 1 to 10,000,000 are lined up, and every fourth one (4=22, and 2 the lowest prime) is crossed off, then every ninth (9=32, as 3 is the next prime), up to and including every 9,840,769th (as 9,840,769=31372, as 3137 is the largest prime under the square root of 10,000,000.) This modified sieve would remove every number in the range that was evenly divisible by at least one square factor, by its smallest prime square factor. Through this method, most submitters calculated a total of 6,079,291 positive counting numbers less than 10,000,000 that are not divisible by the square of another counting number.
The constructive methods were slightly more elegant / less brute force, in that they involved combinatorics. In order for one of the counting numbers less than 10,000,000 not to be divisible by the square of a prime number, it needs to be the product of singleton primes. That is, as a product, it can’t duplicate any of the 446 prime factors from 2 to 3137. Starting with 1 and adding the 446 primes under sqrt(10,000,000) gets you 447. The combination of 446 things choosing 2 at a time without replacement is 99,235 all of which are under 10 million. The combination of 446 primes chosen 3 at a time is 14,686,780, but a large chunk of these combinations have a product larger than 10,000,000. Removing those over 10 million and later, rinse, repeat up to 446 choose 8 (as the product of the lowest 8 primes is just under 10 million) will also get you total of 6,079,291.
Congratulations to Derrick Schneider for properly calculating the count of numbers in this range without square roots. His entry was drawn at random from those that correctly (or at least reasonably correctly) answered the puzzle. Many kudos to the fine folks at ThinkGeek for providing our puzzle incentives — a $50 ThinkGeek gift certificate will soon be on its way to Derrick.
Thanks to everyone that submitted an entry, and happy puzzling!
Liked it? Take a second to support GeekDad and GeekMom on Patreon!
