A121998 -id:A121998 - cp's OEIS frontend

A332003 Number of compositions (ordered partitions) of n into distinct parts having a common factor > 1 with n.

1, 0, 1, 1, 1, 1, 3, 1, 3, 3, 5, 1, 13, 1, 13, 7, 19, 1, 59, 1, 59, 15, 65, 1, 309, 5, 133, 27, 195, 1, 2883, 1, 435, 67, 617, 17, 4133, 1, 1177, 135, 2915, 1, 36647, 1, 3299, 1767, 4757, 1, 52045, 13, 21149, 619, 11307, 1, 187307, 69, 29467, 1179, 30461

Offset: 0

Ilya Gutkovskiy, Feb 04 2020

nonn

			a(6) = 3 because we have [6], [4, 2] and [2, 4].

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Index entries for sequences related to compositions

Cf. A032020, A100347, A121998, A178472, A331885, A331887, A331888, A332002.

a:= proc(n) local b; b:=
      proc(m, i, p) option remember; `if`(m=0, p!, `if`(i<1, 0,
        b(m, i-1, p)+`if`(i>m or igcd(i, n)=1, 0, b(m-i, i-1, p+1))))
      end; forget(b): b(n$2, 0)
    end:
seq(a(n), n=0..63);  # Alois P. Heinz, Feb 04 2020

a[n_] := Module[{b}, b[m_, i_, p_] := b[m, i, p] = If[m == 0, p!, If[i < 1, 0, b[m, i - 1, p] + If[i > m || GCD[i, n] == 1, 0, b[m - i, i - 1, p + 1]]]]; b[n, n, 0]];
a /@ Range[0, 63] (* Jean-François Alcover, Nov 26 2020, after Alois P. Heinz *)

A381499 a(n) = sum of numbers k < n such that 1 < gcd(k,n) < k and rad(k) does not divide n, where rad = A007947.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 6, 6, 6, 0, 10, 0, 28, 28, 42, 0, 39, 0, 65, 65, 80, 0, 102, 45, 126, 96, 159, 0, 111, 0, 210, 148, 210, 138, 253, 0, 280, 221, 338, 0, 342, 0, 411, 366, 444, 0, 547, 140, 563, 403, 601, 0, 700, 344, 708, 512, 750, 0, 751, 0, 868, 703, 930

Offset: 1

Michael De Vlieger, Mar 02 2025

nonn

Analogous to A066760(n), the sum of row n of A133995, and A381497(n), sum of row n of A381094.

			Table of n and a(n) for select n, showing prime power decomposition of the latter and row n of A272619:
 n   a(n)  Factor(a(n))  Row n of A272619
-----------------------------------------------------
 8     6   2 * 3         {6}
 9     6   2 * 3         {6}
10     6   2 * 3         {6}
12    10   2 * 5         {10}
14    28   2^2 * 7       {6,10,12}
15    28   2^2 * 7       {6,10,12}
16    42   2 * 3 * 7     {6,10,12,14}
18    39   3 * 13        {10,14,15}
20    65   5 * 13        {6,12,14,15,18}
21    65   5 * 13        {6,12,14,15,18}
22    80   2^4 * 5       {6,10,12,14,18,20}
24   102   2 * 3 * 17    {10,14,15,20,21,22}
25    45   3^2 * 5       {10,15,20}
26   126   2 * 3^2 * 7   {6,10,12,14,18,20,22,24}
27    96   2^5 * 3       {6,12,15,18,21,24}
28   159   3 * 53        {6,10,12,18,20,21,22,24,26}

Michael De Vlieger, Table of n, a(n) for n = 1..16384
Michael De Vlieger, Log log scatterplot of a(n), n = 8..2^14, ignoring a(n) = 0, showing a(n) for prime power n in gold, a(n) for squarefree n in green, otherwise blue.

Cf. A007947, A038566, A066760, A121998, A243823, A272619, A381497.

rad[x_] := rad[x] = Times @@ FactorInteger[x][[All, 1]]; Table[r = rad[n]; If[PrimeQ[n], 0, Total@ Select[Range[n], And[1 < GCD[#, n] < #, ! Divisible[n, rad[#]]] &]], {n, 120}]

a(n) is the sum of row n of A272619.

a(n) = 0 for prime n, n = 4, and n = 6.

A381803 Number of residues r in {0..n-1} that are not coprime to n and not in row n of A381801.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 3, 0, 4, 0, 1, 0, 4, 1, 0, 0, 6, 3, 0, 6, 8, 0, 4, 0, 11, 5, 8, 0, 9, 0, 0, 10, 13, 0, 7, 0, 9, 7, 11, 0, 17, 5, 3, 0, 12, 0, 6, 8, 21, 1, 0, 0, 17, 0, 25, 15, 26, 8, 15, 0, 24, 11, 12, 0, 29, 0, 0, 7, 17, 3, 22, 0, 32, 23

Offset: 1

Michael De Vlieger, Mar 24 2025

nonn

The intersection of row n of A038566 and row n of A381801 is {1} for n > 1. Therefore most of the terms in row n of A381801 are in row n of A121998 (reading n itself in row n of A121998 instead as n mod n = 0). Thus, a(n) is the number of terms n that are in row n of A121998 but not in A381801.

			Let R(n) = row n of A381801 and let S(n) = row n of A121998, where n in S(n) is instead taken mod n.
a(2) = 0 since S(2) = {} and R(2) = {0, 1}; R(2) \ S(2) is empty.
a(4) = 0 since S(4) = {0, 2} and R(4) = {0, 1, 2}; R(4) \ S(4) is empty.
a(6) = 0 since S(6) = {0, 2, 3, 4} and R(6) = {0, 1, 2, 3, 4} is empty.
a(8) = 1 since S(8) = {0, 2, 4, 6} and R(8) = {0, 1, 2, 4} = {6}.
a(9) = 1 since S(9) = {0, 3, 6} and R(6) = {0, 1, 3} = {6}.
a(10) = 0 since S(10) = {0, 2, 4, 5, 6, 8} and R(10) = {0, 1, 2, 4, 5, 6, 8} is empty.
  Therefore in base 10, numbers k such that rad(k) | 10 (i.e., k in A003592) may end in any number that is not coprime to 10. (Except 1 ends in the digit one, which is coprime to 10).
a(12) = 1 since S(12) = {0, 2, 3, 4, 6, 8, 9, 10} and R(12) = {0, 1, 2, 3, 4, 6, 8, 9} = {10}.
  Therefore in base 12, numbers k such that rad(k) | 12 (i.e., k in A003586) never end in digit 10.
a(14) = 3 since S(14) = {0, 2, 4, 6, 7, 8, 10, 12} and R(14) = {0, 1, 2, 4, 7, 8} = {6, 10, 12}.
  Therefore in base 14, numbers k such that rad(k) | 14 (i.e., k in A003591) never end in digits 6, 10, or 12.
a(16) = 4 since S(16) = {0, 2, 4, 6, 8, 10, 12, 14} and R(14) = {0, 1, 2, 4, 8} = {6, 10, 12, 14}, etc.
  Therefore in hexadecimal, numbers k such that powers of 2 (i.e., A000079) never end in digits 6, 10, 12, or 14.

Michael De Vlieger, Table of n, a(n) for n = 1..10000

Cf. A000010, A038566, A051953, A121998, A381800, A381802.

f[x_] := Block[{c, ff, m, r, p, s, w},
  c[_] := True; ff = FactorInteger[x][[All, 1]]; w = Length[ff];
  s = {1};
  Do[Set[p[i], ff[[i]]], {i, w}];
  Do[Set[s, Union@ Flatten@ Join[s, #[[-1, 1]]]] &@ Reap@
    Do[m = s[[j]];
      While[Sow@ Set[r, Mod[m*p[i], x]];
        c[r],
        c[r] = False;
        m *= p[i]],
       {j, Length[s]}],
    {i, w}]; s ];
{0}~Join~Table[1 + n - EulerPhi[n] - Length@ f[n], {n, 2, 120}]

a(n) = 1 + n - phi(n) - A381800(n)
     = 1 + n - A000010(n) - A381800(n)
     = 1 + A051953(n) - A381800(n)
     = A381802(n) - phi(n) - 1.
a(p) = 0.
a(p^m) = p^(m-1) - m.

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

cp's OEIS Frontend

A332003 Number of compositions (ordered partitions) of n into distinct parts having a common factor > 1 with n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A381499 a(n) = sum of numbers k < n such that 1 < gcd(k,n) < k and rad(k) does not divide n, where rad = A007947.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A381803 Number of residues r in {0..n-1} that are not coprime to n and not in row n of A381801.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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