A038566 -id:A038566 - cp's OEIS frontend

A322165 Numbers k that give record values for s(k)*phi(k)/k^2, where s(k) is the sum of squares of the differences between consecutive totatives of k (A322144).

1, 3, 4, 6, 10, 12, 15, 18, 20, 21, 30, 42, 60, 70, 105, 210, 385, 770, 1155, 2310, 4620, 5005, 10010, 15015, 30030, 60060, 90090, 120120, 150150, 180180, 210210, 240240, 255255, 510510

Offset: 1

Amiram Eldar, Nov 29 2018

Erdős conjectured that this ratio is bounded and offered $500 for a proof. The conjecture was proved by Montgomery and Vaughan, who won the prize.

Is this sequence infinite? If yes, what is lim_{n->oo} s(a(n))*phi(a(n))/a(n)^2?

			The values of the ratio at the first terms of the sequence are 0, 0.222..., 0.5, 0.888..., 0.96, 1, 1.031..., ...

Richard K. Guy, Unsolved Problems in Number Theory, 3rd ed., Springer, 2004, Chapter B40, Gaps between totatives, p. 146.

Paul Erdős, The difference of consecutive primes, Duke Mathematical Journal, Vol. 6, No. 2 (1940), pp. 438-441, alternative link.
Paul Erdős, On the integers relatively prime to n and on a number-theoretic function considered by Jacobsthal, Mathematica Scandinavica, Vol. 10 (1962), pp. 163-170, alternative link.
H. L. Montgomery & R. C. Vaughan, On the distribution of reduced residues, Annals of Mathematics, Vol. 123, No. 2 (1986), pp. 311-333.

Cf. A000010, A038566, A132952, A322144.

ratio[n_] := Module[{v=Differences[Select[Range[n], GCD[n, #] == 1 &]]^2}, Total[v] * (Length[v]+1) / n^2]; seq={}; rm=-1; Do[r=ratio[n]; If[r>rm, rm=r; AppendTo[seq, n]], {n, 1, 1000}]; seq

s(n) = {v = select(x->gcd(x, n)==1, vector(n, k, k)); sum(i=1, #v-1, (v[i+1] - v[i])^2); } \\ A322144
lista(nn) = {my(m = -1); for (n=1, nn, newm = s(n)*eulerphi(n)/n^2; if (newm > m, print1(n, ", "); m = newm););} \\ Michel Marcus, Nov 29 2018

A330733 Triangle read by rows in which row n is the "complete rhythm" of n (see Comments for precise definition).

Original entry on oeis.org

1, 0, 1, 0, 0, 1, 0, 1, 0, 2, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 3, 0, 0, 0, 0, 0, 0, 1, 0, 2, 0, 3, 0, 2, 0, 4, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 1, 0, 1, 1, 1, 0, 1, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 3, 2, 4, 0, 6, 0, 4, 2, 3, 0, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1

Offset: 1

Andrew Hood, Dec 28 2019

Define the "natural rhythm" of any positive integer n to be the sequence consisting of n-1 zeros followed by 1; e.g., the natural rhythm of 5 is [0, 0, 0, 0, 1].
Define the "complete rhythm" of any positive integer n to be the term-by-term sum of the natural rhythm of n and the complete rhythm of f for every proper divisor f of n, extended through n/f cycles so as to give n terms. (Thus the complete rhythm of any noncomposite number is simply its natural rhythm.)
E.g., n=4 has a unique proper factor f=2 (whose complete rhythm is simply its natural rhythm, since 2 is prime).
Thus, for 4, we must add the following two components:
  [0, 0, 0, 1]  (the natural rhythm of 4)
+ [0, 1, 0, 1]  (the rhythm of 2, repeated to give 4 terms)
==============
  [0, 1, 0, 2]  (the complete rhythm of 4).
Right diagonal is A002033 (conjectured).
Any prime column stripped of zeros also yields A002033 (conjectured).
From Michael De Vlieger, Dec 29 2019: (Start)
Positions of 0 in each row n > 1 are in the reduced residue system of n (A038566). Therefore the number of zeros in each row n > 1 is given by the Euler totient function (A000010). This arises because a nonzero addend is introduced for multiples of divisors of n; the numbers k < n such that gcd(k,n) = 1 remain 0.
Conversely, nonzero positions in each row n > 1 are in the cototient of n (A121998), their number given by row n of A051953. (End)

			Here are the rhythms of the first thirteen positive integers:
   1 | 1
   2 | 0,  1
   3 | 0,  0,  1
   4 | 0,  1,  0,  2
   5 | 0,  0,  0,  0,  1
   6 | 0,  1,  1,  1,  0,  3
   7 | 0,  0,  0,  0,  0,  0,  1
   8 | 0,  2,  0,  3,  0,  2,  0,  4
   9 | 0,  0,  1,  0,  0,  1,  0,  0,  2
  10 | 0,  1,  0,  1,  1,  1,  0,  1,  0,  3
  11 | 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1
  12 | 0,  3,  2,  4,  0,  6,  0,  4,  2,  3,  0,  8
  13 | 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1
.
The complete rhythm of 12 is composed as follows:
12 has a "natural rhythm" of
  12 | 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1
12 has proper divisors 2, 3, 4 and 6, whose complete rhythms are
   2 | 0,  1
   3 | 0,  0,  1
   4 | 0,  1,  0,  2
   6 | 0,  1,  1,  1,  0,  3
When the padded (i.e., repeated) rhythms of the proper factors are added to the natural rhythm of 12, we have
   2 | 0,  1,  0,  1,  0,  1,  0,  1,  0,  1,  0,  1
   3 | 0,  0,  1,  0,  0,  1,  0,  0,  1,  0,  0,  1
   4 | 0,  1,  0,  2,  0,  1,  0,  2,  0,  1,  0,  2
   6 | 0,  1,  1,  1,  0,  3,  0,  1,  1,  1,  0,  3
  12 | 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1
  ===+==============================================
  12 | 0,  3,  2,  4,  0,  6,  0,  4,  2,  3,  0,  8

Cf. A002033 (number of perfect partitions of n), A000040 (prime numbers), A000010, A038566, A051953, A121998.

Nest[Function[{a, n, d}, Append[#1, Total@ Map[PadRight[a[[#]], n, a[[#]] ] &, d] + Append[ConstantArray[0, n - 1], 1]]] @@ {#1, #2, Most@ Rest@ Divisors[#2]} & @@ {#, Length@ # + 1} &, {{1}}, 12] // Flatten (* Michael De Vlieger, Dec 29 2019 *)

def memoize(f):
    memo = {}
    def helper(x):
        if x not in memo:
            memo[x] = f(x)
        return memo[x]
    return helper
@memoize
def unique_factors_of(n):
    factors = []
    for candidate in range(2, n//2 + 1):
        if n % candidate == 0:
            factors.append(candidate)
    return factors
@memoize
def is_prime(n):
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i = i + 6
    return True
@memoize
def rhythm(n):
    if n == 0:
        return [0]
    natural_rhythm_of_n = [0]*(n-1)
    natural_rhythm_of_n += [1]
    if is_prime(n):
        return natural_rhythm_of_n
    else:
        component_rhythms = [natural_rhythm_of_n]
        for divisor in unique_factors_of(n):
            component_rhythm = n//divisor * rhythm(divisor)
            component_rhythms.append(component_rhythm)
        return [sum(i) for i in zip(*component_rhythms)]
for i in range(0, 201):
    formatted_string = f'{str(i).rjust(3)}|'
    for note in rhythm(i):
        formatted_string += f'{str(note).rjust(4)}'
    print(formatted_string)

Name clarified by Omar E. Pol and Jon E. Schoenfield, Dec 31 2019

A334428 Irregular triangle read by rows: row n gives the members of the smallest nonnegative reduced residue system in the modified congruence modulo 2n - 1 by Brändli and Beyne, called mod(2*n - 1).

Original entry on oeis.org

0, 1, 1, 2, 1, 2, 3, 1, 2, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 6, 1, 2, 4, 7, 1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 4, 5, 8, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 1, 2, 4, 5, 7, 8, 10, 11, 13, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15

Offset: 1

Wolfdieter Lang, Jun 27 2020

The length of row n is A072451(n) = A055034(2*n-1), for n >= 1.
See the Brändli-Beyne link, and A333856 for the definition and some examples of this mod* system.
This reduced residue system mod* (2*n - 1) will be called RRS*(2*n - 1).
Compare this table with the one for the reduced residue system modulo 2*n - 1 (called RRS(2*n - 1) = A038566(2*n - 1), but with A038566(1) = 0). For n >= 2 RRS*(2*n-1) consists of the first half of the entries of RRS(2*n - 1).
The modular arithmetic is multiplicative but not additive for mod*. See A333856 for examples.

			The irregular triangle T(n, k) begins (b = 2*n - 1):
n    b \k  1 2 3 4 5  6  7  8  9 10 11 12 13 14 15 16 17 18 ...
---------------------------------------------------------------
1    1:    0
2    3:    1
3    5:    1 2
4    7:    1 2 3
5    9:    1 2 4
6   11:    1 2 3 4 5
7   13:    1 2 3 4 5  6
8   15:    1 2 4 7
9   17:    1 2 3 4 5  6  7  8
10  19:    1 2 3 4 5  6  7  8  9
11  21:    1 2 4 5 8 10
12  23:    1 2 3 4 5  6  7  8  9 10 11
13  25:    1 2 3 4 6  7  8  9 11 12
14  27:    1 2 4 5 7  8 10 11 13
15  29:    1 2 3 4 5  6  7  8  9 10 11 12 13 14
16  31:    1 2 3 4 5  6  7  8  9 10 11 12 13 14 15
17  33:    1 2 4 5 7  8 10 13 14 16
18  35:    1 2 3 4 6  8  9 11 12 13 16 17
19  37:    1 2 3 4 5  6  7  8  9 10 11 12 13 14 15 16 17 18
20  39:    1 2 4 5 7  8 10 11 14 16 17 19
...
-----------------------------------------------------------
For n = 5 (b = 9) see the example in A333856.

Gerold Brändli and Tim Beyne, Modified Congruence Modulo n with Half the Amount of Residues, arXiv:1504.02757 [math.NT], 2016.

Cf. A055034, A072451, A038566, A333856.

Array[Function[{m, b}, Select[Range[1, m], GCD[#, b] == 1 &] /. {} -> {0}] @@ {# - 1, 2 # - 1} &, 16] // Flatten (* Michael De Vlieger, Jun 27 2020 *)

T(1, 1) = 0, T(n, k) = A038566(2*n - 1, k) for k = 1, 2, ..., A072451(n), for n >= 2.

cp's OEIS Frontend

A322165 Numbers k that give record values for s(k)*phi(k)/k^2, where s(k) is the sum of squares of the differences between consecutive totatives of k (A322144).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

A330733 Triangle read by rows in which row n is the "complete rhythm" of n (see Comments for precise definition).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Python

Extensions

A334428 Irregular triangle read by rows: row n gives the members of the smallest nonnegative reduced residue system in the modified congruence modulo 2n - 1 by Brändli and Beyne, called mod(2*n - 1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

cp's OEIS Frontend

A322165 Numbers k that give record values for s(k)*phi(k)/k^2, where s(k) is the sum of squares of the differences between consecutive totatives of k (A322144).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

A330733 Triangle read by rows in which row n is the "complete rhythm" of n (see Comments for precise definition).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Python

Extensions

A334428 Irregular triangle read by rows: row n gives the members of the smallest nonnegative reduced residue system in the modified congruence modulo 2*n - 1 by Brändli and Beyne, called mod*(2*n - 1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A334428 Irregular triangle read by rows: row n gives the members of the smallest nonnegative reduced residue system in the modified congruence modulo 2n - 1 by Brändli and Beyne, called mod(2*n - 1).