A328170 -id:A328170 - cp's OEIS frontend

A328172 Number of integer partitions of n with all pairs of consecutive parts relatively prime.

1, 1, 2, 3, 4, 6, 7, 10, 12, 16, 19, 24, 28, 36, 43, 51, 62, 74, 87, 104, 122, 143, 169, 195, 227, 260, 302, 346, 397, 455, 521, 599, 686, 780, 889, 1001, 1138, 1286, 1454, 1638, 1846, 2076, 2330, 2614, 2929, 3280, 3666, 4093, 4565, 5085, 5667, 6300, 7002

Offset: 0

Gus Wiseman, Oct 12 2019

nonn

Except for any number of 1's, these partitions must be strict. The fully strict case is A328188.

Partitions with no consecutive pair of parts relatively prime are A328187, with strict case A328220.

			The a(1) = 1 through a(8) = 12 partitions:
  (1)  (2)   (3)    (4)     (5)      (6)       (7)        (8)
       (11)  (21)   (31)    (32)     (51)      (43)       (53)
             (111)  (211)   (41)     (321)     (52)       (71)
                    (1111)  (311)    (411)     (61)       (431)
                            (2111)   (3111)    (511)      (521)
                            (11111)  (21111)   (3211)     (611)
                                     (111111)  (4111)     (5111)
                                               (31111)    (32111)
                                               (211111)   (41111)
                                               (1111111)  (311111)
                                                          (2111111)
                                                          (11111111)

Alois P. Heinz, Table of n, a(n) for n = 0..1000

The case of compositions is A167606.
The strict case is A328188.
The Heinz numbers of these partitions are given by A328335.
Cf. A000837, A018783, A178470, A328028, A328170, A328171, A328187, A328188 A328220.

b:= proc(n, i, s) option remember; `if`(n=0 or i=1, 1,
      `if`(andmap(j-> igcd(i, j)=1, s), b(n-i, min(n-i, i-1),
           numtheory[factorset](i)), 0)+b(n, i-1, s))
    end:
a:= n-> b(n$2, {}):
seq(a(n), n=0..60);  # Alois P. Heinz, Oct 13 2019

Table[Length[Select[IntegerPartitions[n],!MatchQ[#,{_,x_,y_,_}/;GCD[x,y]>1]&]],{n,0,30}]
(* Second program: *)
b[n_, i_, s_] := b[n, i, s] = If[n == 0 || i == 1, 1,
     If[AllTrue[s, GCD[i, #] == 1&], b[n - i, Min[n - i, i - 1],
     FactorInteger[i][[All, 1]]], 0] + b[n, i - 1, s]];
a[n_] := b[n, n, {}];
a /@ Range[0, 60] (* Jean-François Alcover, May 10 2021, after Alois P. Heinz *)

A328187 Number of integer partitions of n with no pair of consecutive parts relatively prime.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 4, 1, 5, 3, 8, 1, 14, 1, 16, 9, 22, 3, 38, 4, 46, 19, 58, 9, 94, 18, 106, 41, 144, 28, 221, 37, 246, 92, 318, 87, 465, 95, 530, 198, 693, 169, 963, 220, 1108, 424, 1383, 381, 1899, 492, 2216, 815, 2732, 799, 3644, 1041, 4231, 1585, 5194, 1608

Offset: 0

Gus Wiseman, Oct 12 2019

nonn

			The a(1) = 1 through a(15) = 9 partitions (A..F = 10..15):
  1  2  3  4   5  6    7  8     9    A      B  C       D  E        F
           22     33      44    63   55        66         77       96
                  42      62    333  64        84         86       A5
                  222     422        82        93         A4       C3
                          2222       442       A2         C2       555
                                     622       444        644      663
                                     4222      633        662      933
                                     22222     642        842      6333
                                               822        A22      33333
                                               3333       4442
                                               4422       6422
                                               6222       8222
                                               42222      44222
                                               222222     62222
                                                          422222
                                                          2222222

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..300

The Heinz numbers of these partitions are given by A328336.
The case of compositions is A178470.
The strict case is A328220.
Partitions with all pairs of consecutive parts relatively prime are A328172.
Cf. A000837, A018783, A328028, A328170, A328171, A328188.

Table[Length[Select[IntegerPartitions[n],!MatchQ[#,{_,x_,y_,_}/;GCD[x,y]==1]&]],{n,0,30}]

A258409 Greatest common divisor of all (d-1)'s, where the d's are the positive divisors of n.

Original entry on oeis.org

1, 2, 1, 4, 1, 6, 1, 2, 1, 10, 1, 12, 1, 2, 1, 16, 1, 18, 1, 2, 1, 22, 1, 4, 1, 2, 1, 28, 1, 30, 1, 2, 1, 2, 1, 36, 1, 2, 1, 40, 1, 42, 1, 2, 1, 46, 1, 6, 1, 2, 1, 52, 1, 2, 1, 2, 1, 58, 1, 60, 1, 2, 1, 4, 1, 66, 1, 2, 1, 70, 1, 72, 1, 2, 1, 2, 1, 78, 1

Offset: 2

Ivan Neretin, May 29 2015

nonn

a(n) = 1 for even n; a(p) = p-1 for prime p.
a(n) is even for odd n (since all divisors of n are odd).
It appears that a(n) = A052409(A005179(n)), i.e., it is the largest integer power of the smallest number with exactly n divisors. - Michel Marcus, Nov 10 2015
Conjecture: GCD of all (p-1) for prime p|n. - Thomas Ordowski, Sep 14 2016
Conjecture is true, because the set of numbers == 1 (mod g) is closed under multiplication. - Robert Israel, Sep 14 2016
Conjecture: a(n) = A289508(A328023(n)) = GCD of the differences between consecutive divisors of n. See A328163 and A328164. - Gus Wiseman, Oct 16 2019

			65 has divisors 1, 5, 13, and 65, hence a(65) = gcd(1-1,5-1,13-1,65-1) = gcd(0,4,12,64) = 4.

Ivan Neretin, Table of n, a(n) for n = 2..10000

Cf. A049559, A057237, A060680, A063994, A187730, A027750.
Cf. A084190 (similar but with LCM).
Looking at prime indices instead of divisors gives A328167.
Partitions whose parts minus 1 are relatively prime are A328170.
Cf. A000005, A060681, A060683, A193829, A289508.

a258409 n = foldl1 gcd $ map (subtract 1) $ tail $ a027750_row' n
-- Reinhard Zumkeller, Jun 25 2015

f:= n -> igcd(op(map(`-`,numtheory:-factorset(n),-1))):
map(f, [$2..100]); # Robert Israel, Sep 14 2016

Table[GCD @@ (Divisors[n] - 1), {n, 2, 100}]

a(n) = my(g=0); fordiv(n, d, g = gcd(g, d-1)); g; \\ Michel Marcus, May 29 2015

a(n) = gcd(apply(x->x-1, divisors(n))); \\ Michel Marcus, Nov 10 2015

a(n)=if(n%2==0, return(1)); if(n%3==0, return(2)); if(n%5==0 && n%4 != 1, return(2)); gcd(apply(p->p-1, factor(n)[,1])) \\ Charles R Greathouse IV, Sep 19 2016

A328220 Number of strict integer partitions of n with no pair of consecutive parts relatively prime.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 2, 1, 2, 2, 3, 1, 5, 1, 5, 4, 6, 3, 10, 3, 11, 7, 12, 3, 19, 5, 18, 12, 23, 9, 36, 11, 33, 21, 40, 20, 58, 19, 58, 35, 70, 31, 98, 36, 101, 65, 112, 56, 155, 64, 164, 97, 188, 88, 250, 112, 256, 157, 293, 145, 392, 163, 399, 241, 461, 242

Offset: 0

Gus Wiseman, Oct 14 2019

nonn

			The a(2) = 1 through a(20) = 11 partitions (A..K = 10..20):
  2  3  4  5  6   7  8   9   A   B  C    D  E    F   G    H    I    J    K
              42     62  63  64     84      86   96  A6   863  A8   964  C8
                             82     93      A4   A5  C4   962  C6   A63  E6
                                    A2      C2   C3  E2        E4        F5
                                    642     842      862       F3        G4
                                                     A42       G2        I2
                                                               864       A64
                                                               963       A82
                                                               A62       C62
                                                               C42       E42
                                                                         8642

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..500

The non-strict case is A328187.
Partitions with all consecutive parts relatively prime are A328172, with strict case A328188.
Strict partitions with relatively prime parts are A078374.
Partitions with no consecutive divisibilities are A328171.
Cf. A000837, A018783, A070211, A289509, A318980, A325545, A328170, A328221, A328335, A328336.

Table[Length[Select[IntegerPartitions[n],UnsameQ@@#&&!MatchQ[#,{_,x_,y_,_}/;GCD[x,y]==1]&]],{n,0,30}]

A328168 Numbers whose prime indices minus 1 are relatively prime.

Original entry on oeis.org

3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 35, 36, 39, 42, 45, 48, 51, 54, 57, 60, 63, 65, 66, 69, 70, 72, 75, 77, 78, 81, 84, 87, 90, 91, 93, 95, 96, 99, 102, 105, 108, 111, 114, 117, 120, 123, 126, 129, 130, 132, 133, 135, 138, 140, 141, 143, 144, 145, 147

Offset: 1

Gus Wiseman, Oct 08 2019

nonn

A multiset is relatively prime if the GCD of its elements is 1. Zeros are ignored when computing GCD, and the empty set has GCD 0.
A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.
The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k), so these are Heinz numbers of partitions whose parts minus one are relatively prime. The enumeration of these partitions by sum is given by A328170.

			The sequence of terms together with their prime indices begins:
    3: {2}
    6: {1,2}
    9: {2,2}
   12: {1,1,2}
   15: {2,3}
   18: {1,2,2}
   21: {2,4}
   24: {1,1,1,2}
   27: {2,2,2}
   30: {1,2,3}
   33: {2,5}
   35: {3,4}
   36: {1,1,2,2}
   39: {2,6}
   42: {1,2,4}
   45: {2,2,3}
   48: {1,1,1,1,2}
   51: {2,7}
   54: {1,2,2,2}
   57: {2,8}

Positions of 1's in A328167.
Numbers whose prime indices are relatively prime are A289509.
The version for prime indices plus 1 is A318981.
The GCD of prime indices is A289508.
Partitions whose parts minus 1 are relatively prime are A328170.
Cf. A000837, A056239, A112798, A258409, A281116, A290103, A328163, A328169.

q:= n-> igcd(map(i-> numtheory[pi](i[1])-1, ifactors(n)[2])[])=1:
select(q, [$1..150])[];  # Alois P. Heinz, Oct 13 2019

Select[Range[100],GCD@@(PrimePi/@First/@If[#==1,{},FactorInteger[#]]-1)==1&]

A328188 Number of strict integer partitions of n with all pairs of consecutive parts relatively prime.

Original entry on oeis.org

1, 1, 1, 2, 2, 3, 3, 4, 5, 6, 7, 8, 9, 12, 15, 15, 19, 23, 25, 30, 35, 39, 47, 52, 58, 65, 75, 86, 95, 109, 124, 144, 165, 181, 203, 221, 249, 285, 316, 352, 392, 438, 484, 538, 599, 666, 737, 813, 899, 992, 1102, 1215, 1335, 1472, 1621, 1776, 1946, 2137, 2336

Offset: 0

Gus Wiseman, Oct 13 2019

nonn

			The a(1) = 1 through a(15) = 15 partitions (A..F = 10..15):
  1  2  3   4   5   6    7   8    9    A     B     C    D     E     F
        21  31  32  51   43  53   54   73    65    75   76    95    87
                41  321  52  71   72   91    74    B1   85    B3    B4
                         61  431  81   532   83    543  94    D1    D2
                             521  432  541   92    651  A3    653   E1
                                  531  721   A1    732  B2    743   654
                                       4321  731   741  C1    752   753
                                             5321  831  652   761   852
                                                   921  751   851   951
                                                        832   941   A32
                                                        5431  A31   B31
                                                        7321  B21   6531
                                                              5432  7431
                                                              6521  7521
                                                              8321  54321

Alois P. Heinz, Table of n, a(n) for n = 0..1000

The case of compositions is A167606.
The non-strict case is A328172.
The Heinz numbers of these partitions are given by A328335.
Partitions with no pairs of consecutive parts relatively prime are A328187.
Cf. A000837, A018783, A178470, A328028, A328170, A328171, A328187, A328220.

b:= proc(n, i, s) option remember; `if`(i*(i+1)/2 igcd(i, j)=1, s), b(n-i, min(n-i, i-1),
           numtheory[factorset](i)), 0)+b(n, i-1, s)))
    end:
a:= n-> b(n$2, {}):
seq(a(n), n=0..60);  # Alois P. Heinz, Oct 13 2019

Table[Length[Select[IntegerPartitions[n],UnsameQ@@#&&!MatchQ[#,{_,x_,y_,_}/;GCD[x,y]>1]&]],{n,0,30}]
(* Second program: *)
b[n_, i_, s_] := b[n, i, s] = If[i(i + 1)/2 < n, 0, If[n == 0, 1, If[AllTrue[s,  GCD[i, #] == 1&], b[n - i, Min[n - i, i - 1], FactorInteger[i][[All, 1]]], 0] + b[n, i - 1, s]]];
a[n_] := b[n, n, {}];
a /@ Range[0, 60] (* Jean-François Alcover, May 10 2021, after Alois P. Heinz *)

A328167 GCD of the prime indices of n, all minus 1.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Oct 08 2019

nonn

Zeros are ignored when computing GCD, and the empty set has GCD 0.

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.

			85 has prime indices {3,7}, so a(85) = GCD(2,6) = 2.

Positions of 0's are A000079.
Positions of 1's are A328168.
Positions of records (first appearances) are A006005.
The GCD of the prime indices of n is A289508(n).
The GCD of the prime indices of n, all plus 1, is A328169(n).
Looking at divisors instead of prime indices gives A258409.
Partitions whose parts minus 1 are relatively prime are A328170.
Cf. A000837, A001222, A007359, A056239, A112798, A289509, A318978, A318981, A328163, A328164.

Table[GCD@@(PrimePi/@First/@If[n==1,{},FactorInteger[n]]-1),{n,100}]

A328163 Number of integer partitions of n whose unsigned differences have a different GCD than the GCD of their parts all minus 1.

Original entry on oeis.org

0, 0, 1, 1, 2, 1, 4, 2, 5, 5, 9, 5, 15, 9, 19, 16, 28, 16, 44, 21, 55, 38, 73, 34, 109, 46, 130, 73, 170, 66, 251, 78, 287, 137, 364, 119, 522, 135, 590, 236, 759, 190, 1042, 219, 1175, 425, 1460, 306, 2006, 347, 2277, 671, 2780, 471, 3734, 584, 4197, 1087

Offset: 0

Gus Wiseman, Oct 07 2019

nonn

Zeros are ignored when computing GCD, and the empty set has GCD 0.

			The a(2) = 1 through a(12) = 15 partitions (A = 10, B = 11, C = 12):
  (2)  (3)  (4)   (5)  (6)    (7)   (8)     (9)    (A)      (B)     (C)
            (22)       (33)   (52)  (44)    (63)   (55)     (83)    (66)
                       (42)         (62)    (72)   (64)     (92)    (84)
                       (222)        (422)   (333)  (73)     (722)   (93)
                                    (2222)  (522)  (82)     (5222)  (A2)
                                                   (442)            (444)
                                                   (622)            (552)
                                                   (4222)           (633)
                                                   (22222)          (642)
                                                                    (822)
                                                                    (3333)
                                                                    (4422)
                                                                    (6222)
                                                                    (42222)
                                                                    (222222)

The complement to these partitions is counted by A328164.
The GCD of the divisors of n all minus 1 is A258409(n).
The GCD of the prime indices of n all minus 1 is A328167(n).
Partitions whose parts minus 1 are relatively prime are A328170.
Cf. A000837, A018783, A175342, A279945, A289508, A328168, A328169.

Table[Length[Select[IntegerPartitions[n],GCD@@Differences[#]!=GCD@@(#-1)&]],{n,0,30}]

A328164 Number of integer partitions of n whose unsigned differences have the same GCD as the GCD of their parts all minus 1.

Original entry on oeis.org

1, 1, 1, 2, 3, 6, 7, 13, 17, 25, 33, 51, 62, 92, 116, 160, 203, 281, 341, 469, 572, 754, 929, 1221, 1466, 1912, 2306, 2937, 3548, 4499, 5353, 6764, 8062, 10006, 11946, 14764, 17455, 21502, 25425, 30949, 36579, 44393, 52132, 63042, 74000, 88709, 104098, 124448

Offset: 0

Gus Wiseman, Oct 07 2019

nonn

Zeros are ignored when computing GCD, and the empty set has GCD 0.

			The a(1) = 1 through a(8) = 17 partitions:
  (1)  (11)  (21)   (31)    (32)     (51)      (43)       (53)
             (111)  (211)   (41)     (321)     (61)       (71)
                    (1111)  (221)    (411)     (322)      (332)
                            (311)    (2211)    (331)      (431)
                            (2111)   (3111)    (421)      (521)
                            (11111)  (21111)   (511)      (611)
                                     (111111)  (2221)     (3221)
                                               (3211)     (3311)
                                               (4111)     (4211)
                                               (22111)    (5111)
                                               (31111)    (22211)
                                               (211111)   (32111)
                                               (1111111)  (41111)
                                                          (221111)
                                                          (311111)
                                                          (2111111)
                                                          (11111111)

The complement to these partitions is counted by A328163.
The GCD of the divisors of n all minus 1 is A258409(n).
The GCD of the prime indices of n all minus 1 is A328167(n).
Partitions whose parts minus 1 are relatively prime are A328170.
Cf. A000837, A018783, A175342, A279945, A289508, A328168, A328169.

Table[Length[Select[IntegerPartitions[n],GCD@@Differences[#]==GCD@@(#-1)&]],{n,0,30}]

A328451 Sorted positions of first appearances in A328219, where if n = A000040(i_1) * ... * A000040(i_k), then A328219(n) = LCM(1+i_1,...,1+i_k).

Original entry on oeis.org

1, 2, 3, 5, 6, 7, 13, 14, 15, 17, 19, 21, 26, 29, 35, 37, 38, 39, 42, 47, 51, 53, 58, 61, 65, 74, 78, 79, 87, 89, 91, 95, 101, 105, 106, 107, 111, 113, 119, 122, 127, 133, 141, 145, 151, 158, 159, 173, 174, 178, 181, 182, 183, 185, 195, 199, 202, 203, 214, 221

Offset: 1

Gus Wiseman, Oct 17 2019

nonn

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.

Indices of 1's in the ordinal transform of A328219. - Antti Karttunen, Oct 18 2019

			The sequence of terms together with their prime indices begins:
   1: {}
   2: {1}
   3: {2}
   5: {3}
   6: {1,2}
   7: {4}
  13: {6}
  14: {1,4}
  15: {2,3}
  17: {7}
  19: {8}
  21: {2,4}
  26: {1,6}
  29: {10}
  35: {3,4}
  37: {12}
  38: {1,8}
  39: {2,6}
  42: {1,2,4}
  47: {15}

A subsequence of A005117.
Sorted positions of first appearances in A328219.
The GCD of the prime indices of n, all plus 1, is A328169(n).
The LCM of the prime indices of n, all minus 1, is A328456(n).
Partitions whose parts plus 1 are relatively prime are A318980.
Numbers whose prime indices plus 1 are relatively prime are A318981.
Cf. A001222, A056239, A112798, A289508, A289509, A290103, A328163, A328167, A328168, A328170.

dav=Table[If[n==1,1,LCM@@(PrimePi/@First/@FactorInteger[n]+1)],{n,100}];
Table[Position[dav,i][[1,1]],{i,dav//.{A___,x_,B___,x_,C___}:>{A,x,B,C}}]

up_to = 1024;
ordinal_transform(invec) = { my(om = Map(), outvec = vector(length(invec)), pt); for(i=1, length(invec), if(mapisdefined(om,invec[i]), pt = mapget(om, invec[i]), pt = 0); outvec[i] = (1+pt); mapput(om,invec[i],(1+pt))); outvec; };
A003961(n) = my(f = factor(n)); for (i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); factorback(f); \\ From A003961
A290103(n) = lcm(apply(p->primepi(p),factor(n)[,1]));
A328219(n) = A290103(A003961(n));
vord_trans = ordinal_transform(vector(up_to,n,A328219(n)));
for(n=1,up_to,if(1==vord_trans[n], print1(n,", "))); \\ Antti Karttunen, Oct 18 2019

cp's OEIS Frontend

A328172 Number of integer partitions of n with all pairs of consecutive parts relatively prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A328187 Number of integer partitions of n with no pair of consecutive parts relatively prime.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A258409 Greatest common divisor of all (d-1)'s, where the d's are the positive divisors of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

A328220 Number of strict integer partitions of n with no pair of consecutive parts relatively prime.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A328168 Numbers whose prime indices minus 1 are relatively prime.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

A328188 Number of strict integer partitions of n with all pairs of consecutive parts relatively prime.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A328167 GCD of the prime indices of n, all minus 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A328163 Number of integer partitions of n whose unsigned differences have a different GCD than the GCD of their parts all minus 1.

Views

Author

Keywords

Comments

Examples