OEIS A347293 row-sum convolution

Abstract

The row sum of the OEIS A347293 shifted-product gcd triangle equals a divisor convolution of squares and squared totients.

Definition 1.1 (The shifted-product gcd row sum).

$$\forall n\in \mathrm{Nat},\mathrm{rowSum}\left(n\right)=\sum _{x\in \mathrm{range}\left(n\right)}(\sum _{y\in \mathrm{range}\left(n\right)}\gcd \left(1+x\cdot y,n\right))$$

Formalization. D5/S3/ArithSums/SchulteShiftedProductGcdRowSumConvolution.rowSum (✓ std3).

Citation. Werner Schulte (2022). OEIS A347293, shifted-product gcd triangle and row-sum convolution. URL: https://oeis.org/A347293.

Commentary.

The two range sums run over x and y from zero through n minus one. They are the OEIS triangle’s row sum after the index changes x=i-1 and y=k-1.

Theorem 1.2 (The square and squared-totient convolution).

$$\forall n\in \mathrm{Nat},(n>0)\Rightarrow (\mathrm{rowSum}\left(n\right)=\sum _{d\in \mathrm{divisors}\left(n\right)}{d}^2\cdot \mathrm{totient}{\left(n/d\right)}^2)$$

Proof. Machine-checked in Lean as D5/S3/ArithSums/SchulteShiftedProductGcdRowSumConvolution.result (✓ std3). ∎

Resolves. Problems/oeis-a347293-schulte-shifted-product-gcd-row-sum-convolution (proved) by D5/S3/ArithSums/SchulteShiftedProductGcdRowSumConvolution.result.

Citation. Werner Schulte (2022). OEIS A347293, shifted-product gcd triangle and row-sum convolution. URL: https://oeis.org/A347293.

Commentary.

For each divisor d of n, reduction modulo d identifies the pairs with d dividing 1+xy with a unit and its unique negative inverse. There are totient(d) residue pairs and each has (n/d)^2 lifts. Expanding each gcd by the totient divisor sum and reindexing complementary divisors gives the displayed convolution.

References

• Truth anchor: D5/S3/ArithSums/SchulteShiftedProductGcdRowSumConvolution.result
• Truth anchor: D5/S3/ArithSums/SchulteShiftedProductGcdRowSumConvolution.rowSum