20081015, 12:45  #1 
(loop (#_fork))
Feb 2006
Cambridge, England
2·29·109 Posts 
A particularly peculiar problem
Let A = 2*3*5*7*11*13*17*19*23*29*31
Given: a number between 0 and A1, coprime to A Supply: its index 0..phi(A)1 in the set of integers coprime to A listed in increasing order (or in any other order you choose) Please don't use a 31GB lookup table This might actually be useful for singleton removal in very large sets of relations for NFS, though I suspect it's only a moderate improvement (15.2% of numbers in 0..A1 are coprime to A, whilst 26.7% of numbers in 0..29 are coprime to 30) over =(mod(G15,5)1)*2+(mod(G15,6)1)/4 as the reduction from 0..29 to 0..7 for numbers coprime to 30 
20081015, 14:50  #2 
May 2003
10111110010_{2} Posts 
What is the definition of "index" you are using? From your use of \phi(A), I imagine you mean something related to the order modulo A.

20081015, 17:50  #3 
May 2003
2×761 Posts 
Oh, I think I understand what you meant now. Are you saying, "Take the first \phi(A) integers which are coprime to A, in increasing order, and subscript them according to their relationship in the set. Give a simple algorithm for picking the index where an integer occurs in this set."? That seems like an odd request. Especially since you don't care about the order. What information do you really want to get your hands on?

20081015, 23:58  #4 
"Lucan"
Dec 2006
England
6,451 Posts 
Hope this is relevant:
When I first programmed a Sieve of Eratosthanes (at the age of 50 something) I compressed 30 integers into 8 by excluding multiples of 2,3 and 5. Further compression runs into a Law of Diminishing Returns rather rapidly. 
20081016, 00:20  #5 
Jun 2003
4,721 Posts 
Since this is the puzzle forum and all...
We use variable base encoding to achieve this. Let N be the number for which we need to find the index. Compute w(b) = (N mod b)1, for b = 3,5,7,...,31 (no need to bother with 2) Then Index(N) = ((w(3) * (51) + w(5)) * (71) + w(7)) * (111) + w(11) ... This will give you the index. To find N given then index, you need to do the mods to obtain the w() values and then do CRT to get back N. This is NOT in any specific sort order :( Last fiddled with by axn on 20081016 at 00:22 
20081016, 07:12  #6  
(loop (#_fork))
Feb 2006
Cambridge, England
2·29·109 Posts 
Quote:
Actually you need one threestate counter per prime per side, and the 5tritsinabyte trick (since 3^5 is just less than 2^8) would also let you work up to 2^36 using only A=30. 

20081016, 16:00  #7 
Einyen
Dec 2003
Denmark
2,969 Posts 
This might be what you are looking for?
http://www.rsok.com/~jrm/printprimes.html I used the 48bits / 210 integers scheme to pack down all prime numbers up to 10^10 (actually up to 10,000,000,080) in a file taking 285,714,288 bytes. 
20081114, 07:56  #8 
Oct 2008
5 Posts 
It can be done, but it might be slowish. A is the product of 11 primes, which we can number as p1..p11 for convenience. Suppose that n is the number in question. The number of numbers less than n which are divisible by p_i is floor(n/p_i). Similarly, the number of numbers less than n which are divisible by both p_i and p_j is floor(n/(p_i*p_j)). Etc. Suppose that we write K(n,m) for the number of numbers less than n which are divisible by a subset of exactly m primes among p1..p11. This means computing K(n,1)..K(n,10) (assuming that n is less than A). By the rule of inclusion/exclusion, the number of numbers less than n which are divisible by at least one of the primes p1..p11 will be K(n,1)K(n,2)+K(n,3)K(n,4)+...K(n,10). The index of n will then be this number subtracted from n, i.e. the number of numbers less than n which are coprime to A.
As to computational speed. The calculation of K(n,1) involves the sum of 11 numbers of the form floor(n/p_i). Similarly the calculation of K(n,2) involves the sum of 55 numbers of the form floor(n/d), where d is the product of exactly 2 of the p_i. Etc. In general, the calculation of K(n,m) will require the calculation of the sum of C(11,m) numbers of the form floor(n/d), where d is the product of exactly m of the p_i. The total number of summands will be 2^112, which is tolerable. (C(11,m) is a binomial coefficient.) I don't offhand see a simpler approach. There may be a few shortcuts along the way. For the record A = 200560490130, and phi(A) = 30656102400, both of which are too large for 32bit arithmetic. They both fit into doubles, though. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Peculiar activity in the 1M range...  petrw1  PrimeNet  5  20110114 18:01 
Sum of two squares: Peculiar property  Raman  Puzzles  13  20100213 05:25 
Peculiar behaviour of prime numbers .....  spkarra  Math  8  20090720 22:47 
Peculiar Case of Benjamin Button is AWESOME!!!!!!!  jasong  jasong  7  20090101 00:50 
51 problem  Neves  Puzzles  15  20040205 23:11 