Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am working on a modified totient function for counting constellations in reduced residue systems for the same range that Euler's totient function is defined over. This post is separated into three parts: "background" describes how this function was derived and the logic involved, "question" defines the function and questions involved, and "terminology" explains some of the terminology I use, which may or may not be a bit obfuscated.

NOTE: this entire question has been edited in an attempt to improve understandability. If you have any suggestions, please let me know.


Background:

The primorial is defined as the product of all primes that are smaller than or equal to some positive integer; defined for all positive integers, it is written $n\#$, but the convention I have found to be most useful is $P_n\#$, where $P_n$ is the nth prime number, and the function is the product of all prime numbers up to and including $P_n$.

The primorial function can be modified to evaluate Euler's totient function for primorial inputs. The idea is this: the primorial itself can be seen as the product of the number of possible equivalence classes for each prime number. To eliminate those numbers that are divisible by a prime number, we subtract one from each set of equivalence classes modulo a prime number. This is better expressed below:

$$\phi(p_n\#) = \prod_{p|p_n\#} (p - 1)$$

Euler's totient function, in one of its many forms, is written as follows:

$$\phi(p^k) = (p-1)p^{k-1}$$

The difference between the two functions is negligible because primorials, as the products of the primes, have no prime powers in their factors beyond the initial power of 1; this effectively cancels out the $pk-1$ term, leaving only the (p-1). As both functions are measuring the same thing, it is the first function that, while correct, cannot be extended for any positive integer input. The two expressions are equivalent.

The OEIS sequence A059861 is the result of the following expression:

$$\prod_{p|p_n\#} (p - 2)$$

Please take the time to look this up in the OEIS for verification; it calculates the 2 and 4 differences in the differences between the numbers in reduced residue systems for primorials. If we multiply it by 2, we count all of the "twins", that is, each number in the reduced residue system for a primorial that is +2 or -2 away from another number in that same reduced residue system.

We can see these functions a little differently when only considering primorial inputs; there are two possible equivalence classes modulo 2: 0, and 1. There are 3 modulo 3: 0, 1, and 2. If a positive integer is equivalent to 0 modulo 2 or 3 or any other prime, it is divisible by that prime, and must therefore be equal to the prime in question, ir it is not prime itself as it is divisible by that prime. Thus, to count the number of positive integers smaller than the product of 2 and 3, we can take the product of $(2-1)(3-1)=1*2=2$. By subtracting one from each prime number, we have eliminated the equivalence classes modulo those prime numbers that cannot support other prime numbers.

This same process works for counting twins in reduced residue systems for primorials, but instead of subtracting one from each prime in the product, we subtract 2; however, when subtracting 2, we must define the function differently for the first prime number, because otherwise, we will have a zero in our product, and while we don't know if there are infinitely many twin primes, we do know there are a lot of them. To fix this, the term involving the first prime number must be defined to evaluate to 1; we still need to remove all those numbers which are equivalent to 0 mod 2.

Now, what if we were to extend this function to have the capacity to subtract any positive integer k from each prime number in the product? I believe this will create a function that can count constellations in reduced residue systems for primorials. This function is written as follows:

$$p_n\#(-k) = \prod_{a = i}^n (p - k), i = min(\{z|p_z > k\})$$

Remember that in terms of the totient function, we are missing something. To generalize this formula, we need to add that "something" back in (please forgive the notation, as I am unsure of how to write this otherwise):

$$\phi(-k)(n) = \prod_{p|n} (p-k)p^{m-1},$$

where m is the power of p that is a factor of n. There is, however, a problem with that last function; when $p < k$, we introduce negative numbers, and when $p = k$, we introduce zero in our product. This will not do; however, we must be careful in fixing this problem, as the new addition is essential for the generalization of this formula.


Question:

$$\phi(-k)(n) = \left( \prod_{p|n \wedge p \leq k} p^{m-1} \right) \left( \prod_{p|n \wedge p > k} (p - k)p^{m-1} \right),$$

where m is the power of the prime as it appears in the prime factorization of n (in other words, the number of times p shows up in the prime factorization of n)

Questions:

1: is this last formula a valid method of counting constellations in reduced residue systems?

2: Have you seen this in existing literature? If so, please provide a reference!

EDIT: This formula, as stated in my comments to the chosen answer, does not correctly count all elements in a given constellation; it merely counts residues. It may, however, be possible that this formula either does or can be modified to count only the first element in constellations of given forms. The result can then be multiplied by the number of elements in the target constellation to count all members of given constellations in reduced residue systems.


Terminology:

Primorial: the product of prime numbers up to a given limit. The limit can be given as any positive integer n or as a prime number indexed by a subscript.

Phi function, Euler's totient function: The function that counts how many numbers smaller than its input are coprime with that input.

Reduced Residue System: the numbers that the totient function counts relative to some input n.

Twin: as used here, it is any integer n that is a member of a pair of ingeters such that the other member of the pair is either n+2 or n-2.

Constellation: again, as used here, a sequence of consecutive elements of the reduced residue system for a given input that appear according to some pattern; the Hardy-Littlewood k-tuple conjecture states that, given any constellation in the prime numbers, identical patterns will appear in constellations in the primes infinitely many times.

share|improve this question

1 Answer 1

up vote 3 down vote accepted

1: Your formula for $\phi(-k)(n)$ does count the number of reduced residues $a$, modulo the product of the first $n$ primes except for those primes less than or equal to $k$, for which $a+1, \dots, a+k-1$ are all reduced residues. It's a rather specialized situation.

2: For a similar formula that counts $k$-tuples of reduced residues more generally, look at the Prime $k$-tuples Conjecture, particularly the infinite product of primes that appears as a constant in it.

share|improve this answer
    
Excellent answer, voted up. I'm leaving the question open for now for two reasons: the reference given doesn't deal exactly with what I am looking for, but does come close, and I need time to study (1) and figure out if this satisfies my questions. –  Adam Feb 24 '13 at 15:59
    
Fair enough. Part of the confusion (mine, at least) is that you've written down a formula and seem to be asking what problem it corresponds to. I think there's more clarity to be gained by writing down precisely the problem you're interested in and then trying to figure out the relevant formula. –  Greg Martin Feb 24 '13 at 20:21
    
Good point; I'll try to modify my question a little to focus more on the problem: counting constellations in reduced residue systems. It's still nice if it only works for primorials, but I would like to generalize it in the same way that the totient function is generalized. –  Adam Feb 25 '13 at 16:23
    
Chosen as the answer because of (1). The last formula does not count constellations as I had expected, though there may be some aspects to it that are still useful. I am still researching this formula to see what, exactly, it does count. It may be possible to modify it to count only the first element of a constellation and then multiplied by the number of elements in the constellation to count elements of entire constellations, as was the approach for twins. –  Adam Mar 2 '13 at 15:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.