Ideal numbers that can fit into an integer of 64 bits (using priority queues)

Question

How can we print all perfect forces that can be represented as 64-bit integers: 4, 8, 9, 16, 25, 27, ... The ideal force is a number that can be written as ab for integers a and b ≥ 2. This is not a problem with homework, I found it in the interview questions section in the book of algorithm development. Hint: the chapter was based on priority lines.

Most of the ideas that I have are quadratic in nature, which continue to find strength until they stop installing 64 bits, but this is not what the interviewer will look for. Also, I can't figure out how PQ will help here.

Answer 1

Using a low priority queue, with one entry per capacity, is a smart way to list numbers. See the following python code.

import Queue # in Python 3 say: queue pmax, vmax = 10, 150 Q=Queue.PriorityQueue(pmax) p = 2 for e in range(2,pmax): p *= 2 Q.put((p,2,e)) print 1,1,2 while not Q.empty(): (v, b, e) = Q.get() if v < vmax: print v, b, e b += 1 Q.put((b**e, b, e)) 

With pmax, vmax, as in the code above, it produces the following output. For the proposed problem, replace pmax and vmax with 64 and 2**64 .

 1 1 2 4 2 2 8 2 3 9 3 2 16 2 4 16 4 2 25 5 2 27 3 3 32 2 5 36 6 2 49 7 2 64 2 6 64 4 3 64 8 2 81 3 4 81 9 2 100 10 2 121 11 2 125 5 3 128 2 7 144 12 2 

The complexity of this method is O (vmax ^ 0.5 * log (pmax)). This is due to the fact that the number of perfect squares dominates the number of perfect cubes, fourth degrees, etc., And for each square we do O (log (pmax)) work for get and put queue operations. For higher degrees, we do O (log (pmax)) when calculating b**e .

When vmax,pmax =64, 2**64 , operations of the order of 2 * (2 ^ 32 + 2 ^ 21 + 2 ^ 16 + 2 ^ 12 + ...) will be performed, i.e. order of order 2 ^ 33 of the queue.

Added note: this note discusses comment cf16, "only one remark, I do not think that the number of perfect squares is dominant in the number of perfect cubes, fourth degrees, etc.", they are all infinite, but yes, if we consider a finite set ". It’s true that in the general mathematical scheme of things, the powers are the same. That is, if P(j) is the set of all j 'th degrees of integers, then the power P(j) == P(k) for all integers j,k > 0 Elements of any two sets of degrees can be placed in 1-1 with each other.

However, when calculating perfect degrees in ascending order, no matter how many calculated, finite or not, the work of delivering squares dominates that for any other force. For any given x, the density of perfect k ^th degrees in the region x decreases exponentially with increasing k. With increasing x, the density of perfect k ^th degrees in the region x is proportional to (x ^{1 / k} ) / x, therefore, third degrees, fourth degrees, etc. become vanishingly rare compared to squares as x increases.

As a concrete example, among the perfect forces between 1e8 and 1e9, the number (2; 3; 4; 5; 6) of the degree is about (21622; 535; 77; 24; 10). There are more than 30 times more squares between 1e8 and 1e9 than cases of higher powers than squares. Here are the ratios of the number of perfect squares between two numbers, as well as the number of higher perfect degrees: 10¹⁰-10¹⁵, r≈301; 10¹⁵-10²⁰, r≈2K; 10²⁰-10²⁵, r≈15K; 10 ²-10⁰⁰, r≈100K. In short, as x increases, the squares dominate more and more when perfect powers are transmitted in increasing order.

Answer 2

The priority queue helps, for example, if you want to avoid duplicates in the output, or if you want to list values, in particular sorted ones.

Priority queues can often be replaced by sorting and vice versa. Therefore, you can create all combinations ^b, then sort the results and remove adjacent duplicates. In this application, this approach looks a little, but perhaps not dramatically ineffective as one of the sister's answers was discovered.

Priority queuing may be better than sorting if you manage to remove duplicates during your work; or if you want to avoid storing and processing the entire result that will be generated in memory. another sister's answer is an example of the latter, but it can easily be done as with a slight modification.

Here, it makes the difference between an array occupying ~ 16 GB of RAM and a queue with less than 64 elements, occupying at least several kilobytes at worst. Such a huge difference in memory consumption also translates as RAM access time compared to the difference in cache access time, so the memory saving algorithm can end up much faster even if the underlying data structure imposes some overhead, supporting itself and requires more instructions compared to a naive algorithm that uses sorting.

Since the input size is fixed, it is technically impossible for the methods that you considered to be quadratic in nature. The presence of two nested loops does not make the algorithm quadratic until you can say that the upper bound of each such loop is proportional to the size of the input and often not even then). What really matters is how many times the innermost logic is executed.

In this case, competition is between valid constants and impracticable constants.

Answer 3

The only way I can see the priority queue is of great importance, is that you want to print the numbers as they appear, in a strictly increasing order and, of course, without printing the number twice. So you start with a simple generator (which uses a sieve of eratosthenes or some more intelligent method to generate a sequence of 2, 3, 5, 7, 11, ...). You start by putting a triple representing the fact that 2 ^ 2 = 4 in line. Then you repeat the process of removing the smallest element (the three with the lowest exponent) from the queue, printing, increasing the index by one and returning it to the queue (with its priority, determined by the result of the new exposure). You alternate this process with the one that generates new primes as needed (sometimes until p ^ 2 is output).

Since the largest exponential base we can have is 2 ^ 32 (2 ^ 32) ^ 2 = 2 ^ 64, the number of elements in the queue should not exceed the number of primes less than 2 ^ 32, which is obviously 203 280 821 , which I think is an affordable number.