# Is this a paradox on the number line

• I
I've noticed that for every prime and every composite number on the number line that is not a perfect power, ( I am referring to positive whole numbers only), that there are infinitely many perfect powers (PPs) that can be generated using that number. This suggests that the PPs should swamp the primes plus the non-powered composites. However when I compare the relative incidence of PPs along the number line, I find that the further along I go, the fewer PPs show up. e.g. for the first 10 numbers there are 3 PPs: 100 gives 12; 1000 gives 40 ;10,000, 123; 100,000, 368; and 1,000,000, 1109. (I figured these out manually so sums may have errors but the point still holds.) So far there is an obvious decline in the incidence of PPs as we go along the number line. I realize that the number line is infinite and that no matter how far we travel along that line we are barely getting started. That said, it seems apparent to me that the trend won't change until we get way past 'barely getting started', which is not reachable. Is anyone aware of this being explored, or could there be a formula which would predict the number of PPs over a given length of the number line? Thanks in advance.

phinds
Gold Member
2019 Award
I can't answer your question but I suggest that your concepts of "barely getting started" and "way beyond barely getting started" are not meaningful. No matter how far along the line you are, you are exactly the same distance from the end as you were when you started.

mfb
Mentor
've noticed that for every prime and every composite number on the number line that is not a perfect power, ( I am referring to positive whole numbers only), that there are infinitely many perfect powers (PPs) that can be generated using that number.
What do you mean by "generated"?

Both the number of primes and the number of perfect powers is infinite - their number is the same. What you are looking at is the relative frequency within the first N numbers, where there are more primes than perfect powers. Deriving very large perfect powers from small primes doesn't do anything to help there.

Stephen Tashi
This suggests that the PPs should swamp the primes plus the non-powered composites.
Why does it suggest that? You are considering finite intervals. For example, if we generate the powers of 5, they are more and more widely spaced apart. If the powers of numbers were equally spaced on the number line ( as are the multiples of numbers) then intuition would say that they would have a great "density" in a given finite interval. But since the perfect powers don't have constant "density", over intervals, I don't see that intuition can decide about who wins as far as the density perfect powers versus non-perfect powers in a finite interval.

'Barely getting started' Poor choice of words. I think I do understand it the way you put it. I was referring to how far away from beginning I was. Infinity is open ended, (if I can call it that), but only at one extreme. The beginning of the portion of the number line to which I was referring is fixed and I guess I was thinking of how far from it I was while not getting any closer to end.Thanks.
'Generated' what I was trying to suggest is that one could take any number, 3 for example, and square it, cube it ....... infinitely many times, creating an infinite group of perfect numbers to match only one prime. the number of powers of three greatly out number one which is the quantity of the number three. Then repeat for each single prime or other composite which has not yet been raised to a power.
The whole point I was getting at was that the powers spread out too fast creating the impression, to me , that there are fewer powers then other numbers. rather than the other way around which I had expected. Thanks to all.You have given me lots to digest.

Stephen Tashi
The question can be formulated rigorously. Let ##P(N)## be the number of perfect powers of natural numbers that are less than or equal to ##N##. Find ##lim_{N \rightarrow \infty} \frac{P(N)}{(N - P(N))} ## if that limit exists.

fresh_42
Mentor
It seems you all know. What is a perfect power?

Stephen Tashi
It seems you all know. What is a perfect power?
I'm assuming its a natural number that is equal to a natural number power of some other (different) natural number.

fresh_42
Mentor
I'm assuming its a natural number that is equal to a natural number power of some other (different) natural number.
So ##P(10)=3##, i.e. ##a^n## is one and ##a^nb^m## is not? Isn't ##P(100)=12## a bit low then?

Stephen Tashi
So ##P(10)=3##, i.e. ##a^n## is one and ##a^nb^m## is not?
Yes, I want ##P(10) = 3##, the cardinality of ##\{2^2,2^3, 3^2\}##. So, yes, ##a^nb^m## need not be a "perfect power". We'll see what the others say.

fresh_42
Mentor
I see, the trouble is not to count numbers twice etc. Should be bounded by the number of lattice points in a parabola.

Stephen Tashi
I see, the trouble is not to count numbers twice etc. Should be bounded by the number of lattice points in a parabola.
It would be nice to have a recursion: given ##P(N)## find ##P(N+1)##. However, such a recursion might have a lot of if...then cases. Is there a theory that treats recursions like that?

mfb
Mentor
Most perfect powers below N are squares, and the fraction of other perfect powers goes to zero for N to infinity. There are N^(1/2) squares, N^(1/3) cubes and so on, woth some overlap. Up to 1 million there are 1000 squares, 100 cubes, and just 10 numbers in both categories. There are also a few higher powers, e.g. 15 fifth powers, 3 of them (1^10, 2^10, 3^10) overlapping with the squares, and two overlapping with the cubes (1^15, 2^15). With inclusion-exclusion you can count them in a systematic way.

Last edited:
PeroK
Homework Helper
Gold Member
'Barely getting started' Poor choice of words. I think I do understand it the way you put it. I was referring to how far away from beginning I was. Infinity is open ended, (if I can call it that), but only at one extreme. The beginning of the portion of the number line to which I was referring is fixed and I guess I was thinking of how far from it I was while not getting any closer to end.Thanks.
'Generated' what I was trying to suggest is that one could take any number, 3 for example, and square it, cube it ....... infinitely many times, creating an infinite group of perfect numbers to match only one prime. the number of powers of three greatly out number one which is the quantity of the number three. Then repeat for each single prime or other composite which has not yet been raised to a power.
The whole point I was getting at was that the powers spread out too fast creating the impression, to me , that there are fewer powers then other numbers. rather than the other way around which I had expected. Thanks to all.You have given me lots to digest.
Yes, this is a paradox of infinite sets. A simpler example is to consider the set of natural numbers and the set of even numbers:

##\mathbb{N} = \{1, 2, 3, \dots \}##

##S = \{2, 4, 6, \dots \}##

Clearly, we can put ##\mathbb{N}## into one-to-one correspondence with the set ##S##, in that sense, both ##\mathbb{N}## and ##S## have the same "number" of members and are sets of the same "size". More properly, they are sets of the same Cardinality.

Equally, we can see that ##S## is a proper subset of ##\mathbb{N}##. In that sense ##\mathbb{N}## contains "twice as many" members as ##S##.

Your idea takes this a step further. If we take a prime ##p## and define the set:

##P_p = \{p, p^2, p^3 \dots \}##

Then we cleary have a set that can be put into one-to-one correspondence with ##\mathbb{N}##. Just associate ##p^n## with the number ##n##.

If we take the union of all these sets, we have:

##P = P_2 \bigcup P_3 \bigcup P_5 \dots ##

And, yet, ##P \subset \mathbb{N}##

What we've done is shown that ##\mathbb{N}## can contain a whole infinite sequence of sets, all the same cadinality as itself, and still have plenty left over: "most" numbers, after all, are not prime powers.

To put it another way, ##P## is the union of an infinite collection of sets, all the same cardinality as ##\mathbb{N}##, but still only has the same cardinality as ##\mathbb{N}##.

• jbriggs444
I have read, more than once, some about what Cantor had to say about infinite sets (obviously with limited understanding). I will repeat. Hopefully some of what has been said here will help me to take more of it in. Thanks to all.

jbriggs444