A072774
Powers of squarefree numbers.
Original entry on oeis.org
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 21, 22, 23, 25, 26, 27, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 41, 42, 43, 46, 47, 49, 51, 53, 55, 57, 58, 59, 61, 62, 64, 65, 66, 67, 69, 70, 71, 73, 74, 77, 78, 79, 81, 82, 83, 85, 86, 87, 89, 91, 93, 94, 95, 97
Offset: 1
Cf.
A000005,
A000009,
A000837,
A007916,
A013661,
A047966,
A052409,
A052410,
A072774,
A078374,
A289023,
A289509,
A300486,
A302491,
A302796,
A302979.
-
import Data.Map (empty, findMin, deleteMin, insert)
import qualified Data.Map.Lazy as Map (null)
a072774 n = a072774_list !! (n-1)
(a072774_list, a072775_list, a072776_list) = unzip3 $
(1, 1, 1) : f (tail a005117_list) empty where
f vs'@(v:vs) m
| Map.null m || xx > v = (v, v, 1) :
f vs (insert (v^2) (v, 2) m)
| otherwise = (xx, bx, ex) :
f vs' (insert (bx*xx) (bx, ex+1) $ deleteMin m)
where (xx, (bx, ex)) = findMin m
-- Reinhard Zumkeller, Apr 06 2014
-
isA := n -> n=1 or is(1 = nops({seq(p[2], p in ifactors(n)[2])})):
select(isA, [seq(1..97)]); # Peter Luschny, Jun 10 2025
-
Select[Range[100], Length[Union[FactorInteger[#][[All, 2]]]] == 1 &] (* Geoffrey Critzer, Mar 30 2015 *)
-
is(n)=ispower(n,,&n); issquarefree(n) \\ Charles R Greathouse IV, Oct 16 2015
-
from math import isqrt
from sympy import mobius, integer_nthroot
def A072774(n):
def g(x): return int(sum(mobius(k)*(x//k**2) for k in range(1, isqrt(x)+1)))-1
def f(x): return n-2+x-sum(g(integer_nthroot(x,k)[0]) for k in range(1,x.bit_length()))
kmin, kmax = 1,2
while f(kmax) >= kmax:
kmax <<= 1
while True:
kmid = kmax+kmin>>1
if f(kmid) < kmid:
kmax = kmid
else:
kmin = kmid
if kmax-kmin <= 1:
break
return kmax # Chai Wah Wu, Aug 19 2024
A007360
Number of partitions of n into distinct and pairwise relatively prime parts.
Original entry on oeis.org
1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 8, 9, 10, 11, 10, 13, 17, 19, 21, 22, 21, 24, 32, 37, 37, 38, 40, 45, 55, 65, 69, 66, 64, 75, 86, 100, 113, 107, 106, 122, 145, 165, 174, 167, 162, 179, 222, 253, 255, 255, 255, 273, 328, 373, 376, 369, 377, 406, 476, 553, 569, 537, 529
Offset: 1
From _Gus Wiseman_, Sep 23 2019: (Start)
The a(1) = 1 through a(10) = 6 partitions (A = 10):
(1) (2) (3) (4) (5) (6) (7) (8) (9) (A)
(21) (31) (32) (51) (43) (53) (54) (73)
(41) (321) (52) (71) (72) (91)
(61) (431) (81) (532)
(521) (531) (541)
(721)
(End)
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Number of partitions of n into relatively prime parts =
A000837.
Strict relatively prime partitions are
A078374.
Cf.
A007359,
A038348,
A084422,
A186974,
A187106,
A303140,
A302569,
A303362,
A304714,
A320426,
A320436.
-
$RecursionLimit = 1000; b[n_, i_, s_] := b[n, i, s] = Module[{f}, If[n == 0 || i == 1, 1, If[i<2, 0, f = FactorInteger[i][[All, 1]]; b[n, i-1, Select[s, #Jean-François Alcover, Mar 20 2014, after Alois P. Heinz *)
Table[Length[Select[IntegerPartitions[n],Length[#]==1||UnsameQ@@#&&CoprimeQ@@Union[#]&]],{n,0,30}] (* Gus Wiseman, Sep 23 2019 *)
More terms from Pab Ter (pabrlos2(AT)yahoo.com), Nov 13 2005
A305713
Number of strict integer partitions of n into pairwise coprime parts.
Original entry on oeis.org
1, 0, 1, 1, 2, 2, 3, 4, 4, 5, 7, 8, 9, 10, 9, 12, 16, 18, 20, 21, 20, 23, 31, 36, 36, 37, 39, 44, 54, 64, 68, 65, 63, 74, 85, 99, 112, 106, 105, 121, 144, 164, 173, 166, 161, 178, 221, 252, 254, 254, 254, 272, 327, 372, 375, 368, 376, 405, 475, 552, 568, 536
Offset: 1
The a(13) = 9 strict partitions are (7,6), (8,5), (9,4), (10,3), (11,2), (12,1), (7,5,1), (5,4,3,1), (7,3,2,1).
A220377
Number of partitions of n into three distinct and mutually relatively prime parts.
Original entry on oeis.org
1, 0, 2, 1, 3, 1, 6, 1, 7, 3, 7, 3, 14, 3, 15, 6, 14, 6, 25, 6, 22, 10, 25, 9, 42, 8, 34, 15, 37, 15, 53, 13, 48, 22, 53, 17, 78, 17, 65, 30, 63, 24, 99, 24, 88, 35, 84, 30, 126, 34, 103, 45, 103, 38, 166, 35, 124, 57, 128, 51, 184, 44, 150, 67, 172, 52, 218
Offset: 6
For n=10 we have three such partitions: 1+2+7, 1+4+5 and 2+3+5.
From _Gus Wiseman_, Oct 14 2020: (Start)
The a(6) = 1 through a(20) = 15 triples (empty column indicated by dot, A..H = 10..17):
321 . 431 531 532 731 543 751 743 753 754 971 765 B53 875
521 541 651 752 951 853 B51 873 B71 974
721 732 761 B31 871 D31 954 D51 A73
741 851 952 972 A91
831 941 B32 981 B54
921 A31 B41 A71 B72
B21 D21 B43 B81
B52 C71
B61 D43
C51 D52
D32 D61
D41 E51
E31 F41
F21 G31
H21
(End)
A101271 is the relative prime instead of pairwise coprime version.
A305713 counts these partitions of any length, with Heinz numbers
A302797.
A337461 is the non-strict ordered version.
A337605 is the pairwise non-coprime instead of pairwise coprime version.
A001399(n-6) counts strict 3-part partitions, with Heinz numbers
A007304.
A008284 counts partitions by sum and length, with strict case
A008289.
A318717 counts pairwise non-coprime strict partitions.
A326675 ranks pairwise coprime sets.
A327516 counts pairwise coprime partitions.
A337601 counts 3-part partitions whose distinct parts are pairwise coprime.
-
Table[Length@Select[ IntegerPartitions[ n, {3}], #[[1]] != #[[2]] != #[[3]] && GCD[#[[1]], #[[2]]] == 1 && GCD[#[[1]], #[[3]]] == 1 && GCD[#[[2]], #[[3]]] == 1 &], {n, 6, 100}]
Table[Count[IntegerPartitions[n,{3}],?(CoprimeQ@@#&&Length[ Union[#]] == 3&)],{n,6,100}] (* _Harvey P. Dale, May 22 2020 *)
-
a(n)=my(P=partitions(n));sum(i=1,#P,#P[i]==3&&P[i][1]Charles R Greathouse IV, Dec 14 2012
A302698
Number of integer partitions of n into relatively prime parts that are all greater than 1.
Original entry on oeis.org
0, 0, 0, 0, 1, 0, 3, 2, 5, 4, 13, 7, 23, 18, 32, 33, 65, 50, 104, 92, 148, 153, 252, 226, 376, 376, 544, 570, 846, 821, 1237, 1276, 1736, 1869, 2552, 2643, 3659, 3887, 5067, 5509, 7244, 7672, 10086, 10909, 13756, 15168, 19195, 20735, 26237, 28708, 35418, 39207
Offset: 1
The a(5) = 1 through a(12) = 7 partitions (empty column indicated by dot):
(32) . (43) (53) (54) (73) (65) (75)
(52) (332) (72) (433) (74) (543)
(322) (432) (532) (83) (552)
(522) (3322) (92) (732)
(3222) (443) (4332)
(533) (5322)
(542) (33222)
(632)
(722)
(3332)
(4322)
(5222)
(32222)
A000837 is the version allowing 1's.
A002865 does not require relative primality.
A302697 gives the Heinz numbers of these partitions.
A337451 is the ordered strict version.
A337485 is the pairwise coprime instead of relatively prime version.
A000740 counts relatively prime compositions.
A078374 counts relatively prime strict partitions.
A212804 counts compositions with no 1's.
A291166 appears to rank relatively prime compositions.
A332004 counts strict relatively prime compositions.
A337561 counts pairwise coprime strict compositions.
-
b:= proc(n, i, g) option remember; `if`(n=0, `if`(g=1, 1, 0),
`if`(i<2, 0, b(n, i-1, g)+b(n-i, min(n-i, i), igcd(g, i))))
end:
a:= n-> b(n$2, 0):
seq(a(n), n=1..60); # Alois P. Heinz, Apr 12 2018
-
Table[Length[Select[IntegerPartitions[n],FreeQ[#,1]&&GCD@@#===1&]],{n,30}]
(* Second program: *)
b[n_, i_, g_] := b[n, i, g] = If[n == 0, If[g == 1, 1, 0], If[i < 2, 0, b[n, i - 1, g] + b[n - i, Min[n - i, i], GCD[g, i]]]];
a[n_] := b[n, n, 0];
Array[a, 60] (* Jean-François Alcover, May 10 2021, after Alois P. Heinz *)
A305148
Number of integer partitions of n whose distinct parts are pairwise indivisible.
Original entry on oeis.org
1, 1, 2, 2, 3, 3, 4, 5, 6, 7, 9, 12, 12, 17, 20, 22, 28, 35, 39, 48, 55, 65, 79, 90, 105, 121, 143, 166, 190, 219, 254, 290, 332, 382, 436, 493, 567, 637, 729, 824, 931, 1052, 1186, 1334, 1504, 1691, 1894, 2123, 2380, 2664, 2968, 3319, 3704, 4119, 4586, 5110
Offset: 0
The a(9) = 7 integer partitions are (9), (72), (54), (522), (333), (3222), (111111111).
Cf.
A000837,
A001055,
A001970,
A007359,
A007716,
A051424,
A078374,
A100953,
A285572,
A285573,
A302696,
A303362,
A305079,
A305149,
A305150.
-
Table[Length[Select[IntegerPartitions[n],Select[Tuples[Union[#],2],UnsameQ@@#&&Divisible@@#&]=={}&]],{n,20}]
A307719
Number of partitions of n into 3 mutually coprime parts.
Original entry on oeis.org
0, 0, 0, 1, 1, 1, 2, 1, 3, 2, 4, 2, 7, 2, 8, 4, 8, 4, 15, 4, 16, 7, 15, 7, 26, 7, 23, 11, 26, 10, 43, 9, 35, 16, 38, 16, 54, 14, 49, 23, 54, 18, 79, 18, 66, 31, 64, 25, 100, 25, 89, 36, 85, 31, 127, 35, 104, 46, 104, 39, 167, 36, 125, 58, 129, 52, 185, 45
Offset: 0
There are 2 partitions of 9 into 3 mutually coprime parts: 7+1+1 = 5+3+1, so a(9) = 2.
There are 4 partitions of 10 into 3 mutually coprime parts: 8+1+1 = 7+2+1 = 5+4+1 = 5+3+2, so a(10) = 4.
There are 2 partitions of 11 into 3 mutually coprime parts: 9+1+1 = 7+3+1, so a(11) = 2.
There are 7 partitions of 12 into 3 mutually coprime parts: 10+1+1 = 9+2+1 = 8+3+1 = 7+4+1 = 6+5+1 = 7+3+2 = 5+4+3, so a(12) = 7.
A337599 is the pairwise non-coprime instead of pairwise coprime version.
A337601 only requires the distinct parts to be pairwise coprime.
-
N:= 200: # to get a(0)..a(N)
A:= Array(0..N):
for a from 1 to N/3 do
for b from a to (N-a)/2 do
if igcd(a,b) > 1 then next fi;
ab:= a*b;
for c from b to N-a-b do
if igcd(ab,c)=1 then A[a+b+c]:= A[a+b+c]+1 fi
od od od:
convert(A,list); # Robert Israel, May 09 2019
-
Table[Sum[Sum[Floor[1/(GCD[i, j] GCD[j, n - i - j] GCD[i, n - i - j])], {i, j, Floor[(n - j)/2]}], {j, Floor[n/3]}], {n, 0, 100}]
Table[Length[Select[IntegerPartitions[n,{3}],CoprimeQ@@#&]],{n,0,100}] (* Gus Wiseman, Oct 15 2020 *)
A304711
Heinz numbers of integer partitions whose distinct parts are pairwise coprime.
Original entry on oeis.org
2, 4, 6, 8, 10, 12, 14, 15, 16, 18, 20, 22, 24, 26, 28, 30, 32, 33, 34, 35, 36, 38, 40, 44, 45, 46, 48, 50, 51, 52, 54, 55, 56, 58, 60, 62, 64, 66, 68, 69, 70, 72, 74, 75, 76, 77, 80, 82, 85, 86, 88, 90, 92, 93, 94, 95, 96, 98, 99, 100, 102, 104, 106, 108, 110
Offset: 1
Sequence of all partitions whose distinct parts are pairwise coprime begins (1), (11), (21), (111), (31), (211), (41), (32), (1111), (221), (311), (51), (2111), (61), (411), (321), (11111), (52), (71), (43), (2211), (81), (3111).
Cf.
A000837,
A007359,
A018783,
A051424,
A056239,
A078374,
A101268,
A289508,
A289509,
A298748,
A300486,
A302569,
A302696,
A302698,
A302796,
A302797,
A304709.
A337485
Number of pairwise coprime integer partitions of n with no 1's, where a singleton is not considered coprime unless it is (1).
Original entry on oeis.org
0, 0, 0, 0, 0, 1, 0, 2, 1, 2, 2, 4, 3, 5, 4, 4, 7, 8, 9, 10, 10, 9, 13, 17, 18, 17, 19, 19, 24, 29, 34, 33, 31, 31, 42, 42, 56, 55, 50, 54, 66, 77, 86, 86, 79, 81, 96, 124, 127, 126, 127, 126, 145, 181, 190, 184, 183, 192, 212, 262, 289, 278, 257, 270, 311
Offset: 0
The a(n) partitions for n = 5, 7, 12, 13, 16, 17, 18, 19 (A..H = 10..17):
(3,2) (4,3) (7,5) (7,6) (9,7) (9,8) (B,7) (A,9)
(5,2) (5,4,3) (8,5) (B,5) (A,7) (D,5) (B,8)
(7,3,2) (9,4) (D,3) (B,6) (7,6,5) (C,7)
(A,3) (7,5,4) (C,5) (8,7,3) (D,6)
(B,2) (8,5,3) (D,4) (9,5,4) (E,5)
(9,5,2) (E,3) (9,7,2) (F,4)
(B,3,2) (F,2) (B,4,3) (G,3)
(7,5,3,2) (B,5,2) (H,2)
(D,3,2) (B,5,3)
(7,5,4,3)
A007359 considers all singletons to be coprime.
A337452 is the relatively prime instead of pairwise coprime version, with non-strict version
A302698.
A337563 is the restriction to partitions of length 3.
A002865 counts partitions with no 1's.
A078374 counts relatively prime strict partitions.
-
Table[Length[Select[IntegerPartitions[n],!MemberQ[#,1]&&CoprimeQ@@#&]],{n,0,30}]
A324751
Number of strict integer partitions of n containing no prime indices of the parts.
Original entry on oeis.org
1, 1, 1, 1, 2, 1, 3, 3, 2, 4, 5, 5, 6, 8, 8, 12, 10, 14, 13, 18, 19, 26, 25, 30, 34, 39, 40, 51, 55, 60, 71, 77, 90, 97, 111, 123, 136, 153, 170, 179, 216, 230, 264, 282, 322, 345, 385, 423, 470, 513, 573, 629, 686, 755, 834, 910, 1005, 1095, 1194, 1303, 1433
Offset: 0
The a(1) = 1 through a(13) = 8 strict integer partitions (A...D = 10...13):
1 2 3 4 5 6 7 8 9 A B C D
31 42 43 71 54 64 65 75 76
51 52 63 73 83 84 85
72 82 542 93 94
91 731 A2 B2
B1 643
751
931
Cf.
A000720,
A001462,
A007097,
A074971,
A078374,
A112798,
A276625,
A290822,
A305713,
A306844,
A324764.
-
Table[Length[Select[IntegerPartitions[n],UnsameQ@@#&&Intersection[#,PrimePi/@First/@Join@@FactorInteger/@#]=={}&]],{n,0,30}]
Showing 1-10 of 75 results.
Comments