Modified Euler's Totient function for counting constellations in reduced residue systems

Question

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:

ϕ (p_{n} #) = \prod_{p | p_{n} #} (p - 1)

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

ϕ (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 $p k - 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 = m i n ({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):

ϕ (- 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:

ϕ (- k) (n) = (\prod_{p | n \land p \leq k} p^{m - 1}) (\prod_{p | n \land p > k} (p - k) p^{m - 1}),

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.

Greg Martin · Accepted Answer · 2013-03-02 21:48:39Z

up vote 4 down vote accepted

1: Your formula for $ϕ (- 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.

edited Mar 2 '13 at 21:48

answered Feb 24 '13 at 7:54

Greg Martin

33.8k22959

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

add a comment |

Jesse P Francis · Answer 2 · 2015-11-17 04:58:25Z

I am interested in this topic too, primarily prime sieve mathematics, which happens to tie itself up in reduced residue sets and all kind of other number theoretic topics.

To start off, lets look at the dRRS function on primorials, that is: the differences of a reduced residue system modulo primorials. The dRRS function would basically give us the gap sequence to hit numbers CoPrime to a primorial. It would enable us to get future primes, when folded by addition from 1.

For example, dRRS[Primorial1] is just {2}, if we start from 1 and continue adding 2, we will hit only odd numbers. Effectively, 2 eliminates half of all natural numbers from being prime.

dRRS[Primorial[2]] is {4,2} and allows us to skip any multiplies of BOTH 2 and 3, when folded from 1 by addition. That is, we would go from

$1 \to 5 \to 7 \to 11 \to 13 \to 17 \to 19 \to 23 \to 25$ , etc.. Notice how we hit 25, that is 5 squared. This is very relevant. The dRRS function will allow us to get actual primes but only until the next prime squared.

Lets move to how each dRRS result transforms into the next.

For reference:

dRRS[Primorial1] = {2}

To get the dRRS result for the next primorial, we make (next prime = 3) many copies. {2},{2},{2}

Now we add the first two terms. And we get {4,2}

dRRS[Primorial[2]] = {4,2}

Easy huh? Well it doesn't remain this easy. Okay, we are going to repeat the same procedure. Lets make (next prime=5) many copies. {4,2}{4,2}{4,2}{4,2}{4,2}

Now we will multiply {4,2} by 5 as well. We get {20,10} For every sum of 20,10 repeated, we will mark as a set. We do not count the first number though when we are summing, that remains in its own set.

We get {{4}, {2, 4, 2, 4, 2, 4, 2}, {4, 2}}

Now we add neighboring numbers from each set. And we get:

dRRS[Primorial[3]] = {6,4,2,4,2,4,6,2}

The reason I show this procedure even though you might be familiar with the reduced residue sets of primorials, is because this directly shows where the chaos of primes inherently comes from. From partitioning, and copying. Recursively.

Okay, well anyhow, I thought you might want to know that each population has a distinct closed formula equal to sums of products of offset primes. I have not figured out a generic way to generate these, I have only brute-forced them using Mathematica at the moment. But that is what I am looking at next in my search for truth.

Firstly, there are never any consecutive twins, quads, hextuplets, etc, etc ie. the count of {2,2} or {4,4} or {6,6} etc constellations, is always 0, for any dRRS of primorials.

2's and 4's have a count equal to Product[Prime[z] - 2, {z, 2, i}] ( you already know this )

All tuplets have the same count as their palindrome. That is, {2,4} and {4,2} will have equal counts. This is because the dRRS is palindromic itself

Illustrations: ListPlots of dRRS[Primorial[4]], dRRS[Primorial[5]]

the count of {2,4}s is Product[Prime[z] - 3, {z, 3, i}] the count of 6s is 2*Product[Prime[z] - 2, {z, 2, i}] - 2*Product[Prime[z] - 3, {z, 3, i}]

It is clear, because of the partitioning and copying we discussed earlier, that the count of 6s can be derived from the count of constellations {2,4},{4,2}, 2s, and 4s. And so there is clearly a recursive formula that should be able to be derived for the count of any arbitrary constellation.

Again, here are the formulas I currently have, tested up to dRRS[Primorial[10]]


    2 =>   Product[Prime[z] - 2, {z, 2, i}]
    4 =>   Product[Prime[z] - 2, {z, 2, i}]
{2,4} =>   Product[Prime[z] - 3, {z, 3, i}]
{4,2} =>   Product[Prime[z] - 3, {z, 3, i}]
    6 => 2*Product[Prime[z] - 2, {z, 2, i}] - 2*Product[Prime[z] - 3, {z, 3, i}]
{2,6} =>   Product[Prime[z] - 3, {z, 3, i}] +   Product[Prime[z] - 4, {z, 2, i}]
{6,2} =>   Product[Prime[z] - 3, {z, 3, i}] +   Product[Prime[z] - 4, {z, 2, i}]
    8 =>   Product[Prime[z] - 2, {z, 2, i}] - 2*Product[Prime[z] - 3, {z, 3, i}] - Product[Prime[z] - 4, {z, 2, i}]

Another interest fact that I don't know if you are aware of, is that Max[dRRS[Primorial[i]]] is the Jacobsthalian Function of Primorials, seen here: http://oeis.org/A048670

I hope if you are still interested in this topic (which clearly related to the Riemann Hypothesis) that we can maybe put our heads together. Cheers.

For some basic information about writing math at this site see e.g. here, here, here and here. Also, This is a question answer site, and parts like "I hope if you are still interested in this topic (which clearly related to the Riemann Hypothesis) that we can maybe put our heads together. Cheers.", first paragraph etc are not encouraged, even if you have to say it, please use comments instead of putting it in answer. — Jesse P Francis, Nov 17 '15 at 4:55

asked	5 years, 2 months ago
viewed	1,188 times
active	1 month ago

Stack Exchange Network

current community

your communities

more stack exchange communities

Modified Euler's Totient function for counting constellations in reduced residue systems

Background:

Question:

Terminology:

2 Answers 2

Your Answer

Not the answer you're looking for? Browse other questions tagged elementary-number-theory reference-request totient-function prime-twins or ask your own question.

Hot Network Questions

Modified Euler's Totient function for counting constellations in reduced residue systems

Background:

Question:

Terminology:

2 Answers 2

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged elementary-number-theory reference-request totient-function prime-twins or ask your own question.

Related

Hot Network Questions