Talk:Almost prime

Perl 6: Re: solution with identical output based on the factors routine

Hi I was wondering if there is any import or using type statement together with saving factors in a specific named file needed to grant access to factors for the extra code shown or whether the shown code is to be added to the code for factors to get the output. If there is more then could you state it in the intro to the code? Thanks. --Paddy3118 (talk) 22:42, 23 February 2014 (UTC)

Fair enough. Currently just hand inclusion, but expected to change. --TimToady (talk) 01:09, 24 February 2014 (UTC)

K-almost prime entries that are doubled from previous K entries

I was tinkering on how to improve the speed of the computation of larger K-almost primes (both in number of each K-almost prime and the range of Ks of K-almost primes.

I'm sure most people noticed that each successive list of K-primes for a specific K-almost prime,   a certain number of (initial) K-almost primes are merely duplicates of the (first) previous K K-almost primes.

For some K-almost primes:

  K-almost prime   1,       0   "doubles"

  K-almost prime   2,       2

  K-almost prime   3,       4

  K-almost prime   4,       7

  K-almost prime   5,     13

  K-almost prime   6,     22

  K-almost prime   7,     38

  K-almost prime   8,     63

  K-almost prime   9,   102

  K-almost prime 10,   168

  K-almost prime 11,   268

  K-almost prime 12,   426

  K-almost prime 13,   675

  K-almost prime 14, 1064

The question then becomes, how to know determine how many previous entries can be just doubled?   I don't know if there is a formulaic way to compute that number.

Using a known number of previous doubled entries can be a very fast way of computing K-almost primes, considering that for the first 1,064 entries of 14-almost primes, they can be computed directly by just doubling the first 1,064 entries for the 13-almost primes.   -- Gerard Schildberger (talk) 20:37, 11 January 2016 (UTC)

I have   (since the above posting)   added optimization into the 2^nd REXX entry, making it about a hundred times faster.   -- Gerard Schildberger (talk) 02:22, 12 September 2017 (UTC)

In general, you can reduce k when n < OEIS A078843(k). You can repeat to find some r where nth(k,n) = nth(k-r,n) << r. Finding the reduction amount r can be handy when looking at bounds or approximations where you apply the shift at the end.

A similar process can be used with counts, where we find an r s.t. count(k,n) = count(k-r, n>>r), where n < 3^k is used as the test.

One method that works fairly well for large n is to use fast counting methods, then for the nth, use interpolation / binary search. E.g. nth(k=31,n=3e6) in about a second, nth(k=5,n=1e9) in half a second. It seems like there should be a much faster way, similar to quickly generating the nth Hamming number for large n. Danaj (talk) 10:21, 5 July 2020 (UTC)

---