Sequence A007896: Unordered Products of Reduced Proper Fractions With Unreduced Product a/n For Some a

This sequence, Sloane's A7896, is closely related to the sequence A6874 that I found during my early investigations of the Mandelbrot set in the late 1980s (see my Mu-Ency page Enumeration of Features for more information on A6874).

A007896: 1, 1, 2, 3, 4, 4, 6, 7, 9, 8, 10, 12, 12, 12, 16, 18, 16, 19, 18, 24, 24, 20, 22, 32, 30, 24, 34, 36, 28, 40, 30, 42, 40, 32, 48, 60, 36, 36, 48, 64, 40, 60, 42, 60, 76, 44, 46, 86, 63, 66, 64, 72, 52, 82, 80, 96, 72, 56, 58, 128, 60, 60, 114, 104, 96, 100, ...

The sequence counts the number of distinct ways to form a set of reduced proper fractions whose unreduced product has denominator n.

A "proper fraction" is positive and less than 1, i.e. it is not a "complex fraction" like 1²/₃. A product of proper fractions is always another proper fraction.
A "reduced" fraction is in lowest terms, meaning that the numerator and denominator have no common factor. 2/3 is reduced but 4/6 is not.
"Unreduced product" means the product of two or more fractions, without trying to reduce the result. Multiplying 1/2 × 4/3 gives the unreduced product 4/6 (which then could be reduced to 2/3).

To give an example, following are some ways to multiply proper fractions to get an unreduced denominator of 14:

2/7 × 1/2 = 2/14
1/2 × 2/7 = 2/14
5/14 = 5/14

For the purposes of this sequence, the first two are considered to be the same. That is the meaning of the word "unordered" in the title of this article: the fraction-products are unordered because order is not considered significant.

Here is an enumeration of the eligible fraction-products for the first 25 terms of A7896:

A7896(1) = 1: (null product)
A7896(2) = 1: 1/2
A7896(3) = 2: 1/3; 2/3
A7896(4) = 3: 1/2×1/2; 1/4; 3/4
A7896(5) = 4: 1/5; 2/5; 3/5; 4/5
A7896(6) = 4: 1/2×1/3; 1/2×2/3; 1/6; 5/6
A7896(7) = 6: 1/7; 2/7; 3/7; 4/7; 5/7; 6/7
A7896(8) = 7: 1/2×1/2×1/2; 1/2×1/4; 1/2×3/4; 1/8; 3/8; 5/8; 7/8
A7896(9) = 9: 1/3×1/3; 1/3×2/3; 2/3×2/3; 1/9; 2/9; 4/9; 5/9; 7/9; 8/9
A7896(10) = 8: 1/2×1/5; 1/2×2/5; 1/2×3/5; 1/2×4/5; 1/10; 3/10; 7/10; 9/10
A7896(11) = 10: 1/11; 2/11; 3/11; 4/11; 5/11; 6/11; 7/11; 8/11; 9/11; 10/11
A7896(12) = 12: 1/2×1/2×1/3; 1/2×1/2×2/3; 1/2×1/6; 1/2×5/6; 1/3×1/4; 1/3×3/4; 2/3×1/4; 2/3×3/4; 1/12; 5/12; 7/12; 11/12
A7896(13) = 12: 1/13; 2/13; 3/13; 4/13; 5/13; 6/13; 7/13; 8/13; 9/13; 10/13; 11/13; 12/13
A7896(14) = 12: 1/2×1/7; 1/2×2/7; 1/2×3/7; 1/2×4/7; 1/2×5/7; 1/2×6/7; 1/14; 3/14; 5/14; 9/14; 11/14; 13/14
A7896(15) = 16: 1/3×1/5; 1/3×2/5; 1/3×3/5; 1/3×4/5; 2/3×1/5; 2/3×2/5; 2/3×3/5; 2/3×4/5; 1/15; 2/15; 4/15; 7/15; 8/15; 11/15; 13/15; 14/15
A7896(16) = 18: 1/2×1/2×1/2×1/2; 1/2×1/2×1/4; 1/2×1/2×3/4; 1/2×1/8; 1/2×3/8; 1/2×5/8; 1/2×7/8; 1/4×1/4; 1/4×3/4; 3/4×3/4; 1/16; 3/16; 5/16; 7/16; 9/16; 11/16; 13/16; 15/16
A7896(17) = 16: 1/17; 2/17; 3/17; 4/17; 5/17; 6/17; 7/17; 8/17; 9/17; 10/17; 11/17; 12/17; 13/17; 14/17; 15/17; 16/17
A7896(18) = 19: 1/2×1/3×1/3; 1/2×1/3×2/3; 1/2×2/3×2/3; 1/2×1/9; 1/2×2/9; 1/2×4/9; 1/2×5/9; 1/2×7/9; 1/2×8/9; 1/3×1/6; 1/3×5/6; 2/3×1/6; 2/3×5/6; 1/18; 5/18; 7/18; 11/18; 13/18; 17/18
A7896(19) = 18: 1/19; 2/19; 3/19; 4/19; 5/19; 6/19; 7/19; 8/19; 9/19; 10/19; 11/19; 12/19; 13/19; 14/19; 15/19; 16/19; 17/19; 18/19
A7896(20) = 24: 1/2×1/2×1/5; 1/2×1/2×2/5; 1/2×1/2×3/5; 1/2×1/2×4/5; 1/2×1/10; 1/2×3/10; 1/2×7/10; 1/2×9/10; 1/4×1/5; 1/4×2/5; 1/4×3/5; 1/4×4/5; 3/4×1/5; 3/4×2/5; 3/4×3/5; 3/4×4/5; 1/20; 3/20; 7/20; 9/20; 11/20; 13/20; 17/20; 19/20
A7896(21) = 24: 1/3×1/7; 1/3×2/7; 1/3×3/7; 1/3×4/7; 1/3×5/7; 1/3×6/7; 2/3×1/7; 2/3×2/7; 2/3×3/7; 2/3×4/7; 2/3×5/7; 2/3×6/7; 1/21; 2/21; 4/21; 5/21; 8/21; 10/21; 11/21; 13/21; 16/21; 17/21; 19/21; 20/21
A7896(22) = 20: 1/2×1/11; 1/2×2/11; 1/2×3/11; 1/2×4/11; 1/2×5/11; 1/2×6/11; 1/2×7/11; 1/2×8/11; 1/2×9/11; 1/2×10/11; 1/22; 3/22; 5/22; 7/22; 9/22; 13/22; 15/22; 17/22; 19/22; 21/22
A7896(23) = 22: 1/23; 2/23; 3/23; 4/23; 5/23; 6/23; 7/23; 8/23; 9/23; 10/23; 11/23; 12/23; 13/23; 14/23; 15/23; 16/23; 17/23; 18/23; 19/23; 20/23; 21/23; 22/23
A7896(24) = 32: 1/2×1/2×1/2×1/3; 1/2×1/2×1/2×2/3; 1/2×1/2×1/6; 1/2×1/2×5/6; 1/2×1/3×1/4; 1/2×1/3×3/4; 1/2×2/3×1/4; 1/2×2/3×3/4; 1/2×1/12; 1/2×5/12; 1/2×7/12; 1/2×11/12; 1/3×1/8; 1/3×3/8; 1/3×5/8; 1/3×7/8; 2/3×1/8; 2/3×3/8; 2/3×5/8; 2/3×7/8; 1/4×1/6; 1/4×5/6; 3/4×1/6; 3/4×5/6; 1/24; 5/24; 7/24; 11/24; 13/24; 17/24; 19/24; 23/24
A7896(25) = 30: 1/5×1/5; 1/5×2/5; 1/5×3/5; 1/5×4/5; 2/5×2/5; 2/5×3/5; 2/5×4/5; 3/5×3/5; 3/5×4/5; 4/5×4/5; 1/25; 2/25; 3/25; 4/25; 6/25; 7/25; 8/25; 9/25; 11/25; 12/25; 13/25; 14/25; 16/25; 17/25; 18/25; 19/25; 21/25; 22/25; 23/25; 24/25
...

Origin, and Weinstein Terminology

This sequence was developed by Felix Weinstein who sent me a preprint of his paper ¹ in 1994. In it he describes various statistical properties of the Fibonacci partitions (sequence A0119, which has its own page). We had communicated concerning a sequence I had found earlier (sequence A6874 as mentioned above) which is referred to as "Ψ(n)" in a section near the end of later revisions of the paper. This particular sequence appears as "Ψ_c(n)" in that same section.

I could not understand the Weinstein paper enough to get any idea how to calculate Ψ_c(n), though the paper includes this table. The table made it easy to deduce the rules for Ψ_c(n) by comparison to the original Ψ(n), given my experience with the fraction products seen in the Mandelbrot set that generates A6874:

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20

Ψ(n)	1	1	2	3	4	6	6	9	10	12	10	22	12	18	24	27	16	38	18	44
Ψ_c(n)	1	1	2	3	4	4	6	7	9	8	10	12	12	12	16	18	16	19	18	24
Ψ_*(n)	1	1	2	3	3	4	4	7	7	6	6	12	7	8	12	16	9	15	10	18

Looking at the Ψ_c() row and comparing to Ψ(), the differences in columns 6 and 8 are enough to surmise that denominators should be non-decreasing; and column 9 is the first that involves two consecutive denominators greater than 2, which led to the theory that the numerators should increase whenever the denominators are the same. Combined, these two ideas lead to the fairly likely presumption that Ψ_c() is counting unordered series-products as compared to the original Ψ() in which order matters. This agrees with the first 1000 terms in the b-file given in the OEIS entry A7896, and the first 10000 terms (at least) agree with the output of the Pari code, as modified here to actually print out the values:

/* Run this as: /path/to/pari -q a7896.gp */ a(n) = { my(A, v, w, m); if( n<1, 0, v = vector(n, k, k==1); for(k=2, n, m = #digits(n, k) - 1; A = (1 - x)^ -eulerphi(k) + x * O(x^m); w = vector(n); for(i=0, m, w[k^i] = polcoeff(A, i) ); v = dirmul(v, w) ); v[n] ) }; for(i=1, 1000, print(i, " ", a(i));) /* Direct translation from Felix Weinstein's Mathematica code, by Michael Somos, May 26 2014 syntax fixed and final printout loop added by Robert Munafo, 20240315 */

Here is a C program to compute the values by enumerating fraction-products as described above. It runs over 100 times faster than the Pari algorithm, but I have only verified agreement with the Pari for the first 10000 terms.

The Mystery of star-equivalence

Prior to showing the table above, the the Weinstein paper ¹ defines some "equivalence" relationships, of which these two are relevant to us:

The fraction-products a₁/b₁ × a₂/b₂ × ... × a_m/b_m and c₁/d₁ × c₂/d₂ × ... × c_m/d_m are referred to as:

"t-equivalent" if the set {a₁/b₁, a₂/b₂, ... a_m/b_m} is equivalent to the set {c₁/d₁, c₂/d₂, ... c_m/d_m}, i.e. the two are the same if reordered.

"*-equivalent" if the two fraction-products are t-equivalent and if [for all i] b_i=d_i then either a_i=c_i or a_i×c_i is 1 more than a multiple of d_i.

To illustrate the two relationships, here are the simplest examples in which fraction-products are t-equivalent but not *-equivalent or vice versa:

Denominators of 3

2nd f.p:	1/3×1/3	1/3×2/3	2/3×1/3	2/3×2/3
1/3×1/3	t *
1/3×2/3		t *	t
2/3×1/3		t	t *
2/3×2/3				t *

Here, the two that are equivalent by reordering are considered *-equivalent only if they are actually in the same order. A007896 can be said to be defined in terms of t-equivalence because any all fraction-products that are t-equivalent to each other are counted only once. For example, when determining that A007896(9)=9, as shown above, 1/3×2/3 and 2/3×1/3 are t-equivalent, so only one of those is shown in the list of 9 fraction-products: (1/3×1/3, 1/3×2/3, 2/3×2/3, 1/9, 2/9, 4/9, 5/9, 7/9, 8/9). On the other hand, if *-equivalence were used to define such a sequence, then 1/3×2/3 and 2/3×1/3 would be counted separately because they are not *-equivalent, and so A(9) would be 10.

Denominators of 5

2nd f.p:	2/5×2/5	2/5×3/5	3/5×2/5	3/5×3/5
2/5×2/5	t *
2/5×3/5		t *	t *
3/5×2/5		t *	t *
3/5×3/5				t *

Here, the two that are equivalent only by reordering are also considered *-equivalent because 3×2 is one more than a multiple of 5.

The Ψ_*() function is likely defined with the help of the *-equivalent relation, however it does not suffice to simply define Ψ_c() in terms of t-equivalence and then change "t-equivalent" to "*-equivalent" to obtain a definition of Ψ_*(). See my A7898 page for more on this.

1 : Felix V. Weinstein, "Notes on Fibonacci partitions", 1994. Submitted to arXiv at math/0307150 in 2003; revised and expanded through 2018 or later.

This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2024 Apr 12.

s.27