How to list all powerful numbers below N in $O(\sqrt{N})$time?

Arrangements, sorting, packing, partitions, critical path analysis, networks, graphs, ...
Post Reply
castrate
Posts: 21
Joined: Mon Aug 19, 2019 2:34 pm

How to list all powerful numbers below N in $O(\sqrt{N})$time?

Post by castrate »

Powerful numbers: A positive integer n is powerful if $p^2$ is a divisor of n for every prime factor p in n.
From OEIS we know that the number of powerful numbers below N is about $2.1732\sqrt{N}=O(\sqrt{N})$

In fact I do have an algorithm to do so, but some technical issue beats me.
The outline of the algorithm is as follows:

powerful←[1]
primelist←primes below $\sqrt{n}$
for p in primelist:
for powerful_num in powerful:
newpowerful_list←[powerful_num*$p^2$,powerful_num*$p^3$,powerful_num*$p^4$......]
powerful←sorted(powerful+newpowerful_list)//this step costs too much

The marked step aims to keep the order of the powerful number list, but both sorting and binary searching/inserting(which needs to move many numbers in the list) are too time-consuming. This algorithm counts every powerful number only once, for which I think myself on the right track, but due to that step, the algorithm would not be capable for $N>10^{11}$(in fact computing time seems to grow linearly for $N>10^{8}$).

So, how could I optimize my algorithm? Any help is appreciated. :D
pjt33
Posts: 64
Joined: Mon Oct 06, 2008 6:14 pm

Re: How to list all powerful numbers below N in $O(\sqrt{N})$time?

Post by pjt33 »

You don't want to do multiple sorts. What I would try is to use the characterisation that powerful numbers have a canonical representation $a^2 b^3$ where $b$ is squarefree. Calculate the squarefree numbers up to $\sqrt[3]{n}$ and then put these $b$s in a priority queue. For each $b$ the numbers generated by increasing $a$ go in ascending order, so the main loop is to pop a $b$, emit its current value, increment its $a$, and reinsert if below $n$. Time will be within a logarithmic factor of the number of powerful numbers emitted.
Post Reply