Richard Locke Peterson - cp's OEIS frontend

A333468 Length of the largest disjoint cycle of the permutation that results from the composition of first n circular shifts.

1, 2, 2, 3, 5, 6, 3, 4, 9, 4, 7, 10, 9, 14, 4, 5, 7, 18, 8, 10, 7, 7, 14, 11, 6, 26, 12, 9, 29, 30, 5, 6, 33, 11, 21, 6, 11, 15, 22, 27, 41, 6, 17, 8, 8, 7, 22, 24, 15, 50, 28, 8, 53, 18, 22, 14, 25, 9, 15, 55, 14, 50, 6, 7, 65, 11, 19, 34, 69, 23, 35, 14, 22, 74, 10

Offset: 1

Richard Locke Peterson, Mar 22 2020

nonn

Size of the largest part of the partition of n that is associated with the cycle structure of the permutation given by the permutation product (1)*(1,2)*(1,2,3)*...*(1,2,3,...n) after the product is rewritten as the product of disjoint cycles, where * means functional composition, and the permutations are written in cycle form.
Also see Circular shift on Wikipedia.
For n>1, a(n) is always greater than 1, since the given product can never be the identity permutation on the set {1,2,...,n}, which is the only permutation associated with the partition <1,1,...,1> (1 repeated n times).
Connections: The image of 1 in each resulting permutation appears to be the same as the numbers in A003602. The number of parts in the partition associated with each resulting permutation appear to match the numbers in A006694.
The LCM of all cycle lengths gives A051732(n+1). - Alois P. Heinz, Apr 08 2020

			For n=3, the permutation (1)*(1,2)*(1,2,3)=(1)*(2,3), which is associated with the partition <2,1> of 3. The size of the largest part is 2, so a(3)=2.
For n=11, the permutation (1)*(1,2)*..*(1,2,..11)=(1,2,7,5)*(3,4,8,10,11,6,9) when rewritten as the product of disjoint cycles, which is associated with the partition <7,4> of 11. The size of the largest part is 7, so a(11)=7.

Alois P. Heinz, Table of n, a(n) for n = 1..3000
Wikipedia, Circular shift

Cf. A003602, A006694, A051732, A071642, A163782.

Follow(s, f)={my(t=f(s), k=1); while(t>s, k++; t=f(t)); if(s==t, k, 0)}
mkp(n)={my(v=vector(n,i,i)); for(k=1, n, my(t=v[1]); for(i=1, k-1, v[i]=v[i+1]); v[k]=t); v}
a(n)={my(v=mkp(n), m=0); for(i=1, n, m=max(m, Follow(i, j->v[j]))); m} \\ Andrew Howroyd, Mar 27 2020

a(n) = n <=> n in { A163782 } union { 1 }. - Alois P. Heinz, Apr 08 2020

Terms a(20) and beyond from Andrew Howroyd, Mar 27 2020

A326119 a(n) is the absolute value of the alternating sum of the first n increasing perfect powers (A001597): 1, 1-4, 1-4+8, 1-4+8-9, ...

Original entry on oeis.org

1, 3, 5, 4, 12, 13, 14, 18, 18, 31, 33, 48, 52, 69, 56, 72, 72, 97, 99, 117, 108, 135, 121, 168, 156, 187, 174, 226, 215, 269, 243, 286, 290, 335, 341, 388, 396, 445, 455, 506, 494, 530, 559, 597, 628, 668, 663, 706, 738, 783, 817, 864, 864, 900, 949, 987, 1038

Offset: 1

Richard Locke Peterson, Sep 10 2019

nonn

			For n=8: a(8) = |1 - 4 + 8 - 9 + 16 - 25 + 27 - 32|.

Cf. A001597, A076408.

t = Select[Range@2400, # == 1 || GCD @@ Last /@ FactorInteger@# > 1 &]; Abs@ Accumulate[t (-1)^Range@ Length[t]] (* Giovanni Resta, Sep 11 2019 *)

seq(n)={my(v=vector(n), i=0, k=0, s=0); while(i<#v, k++; if(ispower(k)||k==1, s=k-s; i++; v[i]=abs(s))); v} \\ Andrew Howroyd, Sep 10 2019

a(n) = abs(Sum_{k=1..n} (-1)^k*A001597(k)). - Andrew Howroyd, Sep 10 2019

A318296 Number of conjugacy classes of the Sylow 2-subgroup of the alternating group on n letters.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 7, 7, 9, 9, 11, 11, 18, 18

Offset: 1

Richard Locke Peterson, Aug 23 2018

nonn

Also number of partitions of n containing only powers of 2 and having an even number of even elements.

These partitions form a semiring. The semiring uses the following binary operations *,+: Let A=(a1,a2,..,aj) be a partition of k that has j parts with i of those j being powers of 2 greater than 1, written in nonincreasing order. Let B be a partition of y that has x parts, with w of the x being powers of 2 greater than 1, arranged in descending order. Then A+B = (a1,a2,...,aj,b1,b2,...,bx), and A*B=AB=(a1,a2,...,aj)*(b1,b2,...,bx) is defined to be the partition (a1b1,a2b1,...,a1bx,a2b1,...,a2bx,...,ajbx) of ky. Since i and w are even by assumption, the numbers of powers of two in A+B (= i + w) and AB (= ix + jw - iw) must also be even, and both are members of the semiring. In addition, if C = (c1,...cm) is a partition of k into m parts, n of which are powers of two, (AB)C = A(BC) = (a1b1c1,a2b1c1,...,ajbxcm), and (A+B)C = (a1,a2,...,aj,b1,b2,...,bx)(c1,...cm) = (a1c1,a2c1,...,ajcm,b1c1,...) = (a1c1,a2c1,...,ajcm) + (b1c1,b2c1,...,bxcm) = AC + BC, so the necessary criteria for a semiring hold. [Missing parts added by Charlie Neder, Feb 09 2019]

Cf. A018819, A000123, A000041.

a(2n) = a(2n+1) for all n. - Charlie Neder, Feb 09 2019

A316353 Number of partitions of positive integer n such that all parts are less than the square root of n.

Original entry on oeis.org

0, 1, 1, 1, 3, 4, 4, 5, 5, 14, 16, 19, 21, 24, 27, 30, 72, 84, 94, 108, 120, 136, 150, 169, 185, 427, 480, 540, 603, 674, 748, 831, 918, 1014, 1115, 1226, 2702, 3009, 3331, 3692, 4070, 4494, 4935, 5427, 5942, 6510, 7104, 7760, 8442, 18138, 19928, 21873, 23961, 26226, 28652

Offset: 1

Richard Locke Peterson, Jun 29 2018

nonn

This sequence itself is not a semigroup, but the set of all the partitions enumerated by this sequence does form a semigroup (actually a subsemigroup of the set of all partitions) with the following binary operation: let alpha = the partition (a,b,c,... [this is of course a finite list]) be the partition of the number N1 [that is, a + b + c + ... = N1] and let ALPHA = (A,B,C,...) be the partition of N2. Then the binary operation given by alpha*ALPHA = (a,b,c,...)*(A,B,C,...) = (aA,aB,aC,...,bA,bB,bC,...,cA,cB,cC,...) is a partition of the integer N1*N2. Furthermore, since any part x of alpha is less than the square root of N1, and likewise for any part Y of ALPHA, then the part xY is less than the square root of N1*N2, so the set is a subsemigroup of the semigroup of all partitions under the given operation. If the sole partition (1) of 1 is adjoined, the semigroup becomes a monoid.

			a(3)=1, since the partition (1,1,1) is the only partition of 3 with all parts less than the square root of 3 ~ 1.73.
a(6)=4, since there are only 4 allowable partitions: (1,1,1,1,1,1,1), (1,1,1,1,2), (1,1,2,2), and (2,2,2).

Alois P. Heinz, Table of n, a(n) for n = 1..20000 (first 123 terms from Robert G. Wilson v)

Cf. A000041 (the partition numbers), A097356 (with 'no greater' rather than less).

b:= proc(n, i) option remember; `if`(n=0, 1,
      `if`(i<1, 0, b(n, i-1)+b(n-i, min(n-i, i))))
    end:
a:= n-> b(n, (r-> `if`(r*r>=n, r-1, r))(isqrt(n))):
seq(a(n), n=1..100);  # Alois P. Heinz, Aug 02 2018

Table[With[{s = Sqrt@ n}, Count[IntegerPartitions[n], ?(AllTrue[#, # < s &] &)]], {n, 53}] (* _Michael De Vlieger, Jul 22 2018 *)
f[n_] := Length@ IntegerPartitions[n, All, Range@ Sqrt[n - 1]]; Array[f, 50] (* Robert G. Wilson v, Jul 24 2018 *)
b[n_, i_] := b[n, i] = If[n == 0, 1, If[i < 1, 0, b[n, i - 1] + b[n - i, Min[n - i, i]]]];
a[n_] := b[n, Function[r, If[r*r >= n, r - 1, r]][Floor[Sqrt[n]]]];
Array[a, 100] (* Jean-François Alcover, May 30 2021, after Alois P. Heinz *)

a(n) = my(nb = 0); forpart(p=n, nb++, sqrtint(n)-issquare(n)); nb; \\ Michel Marcus, Jul 15 2018

log(a(n)) ~ log(A258268) * sqrt(n) - log(n). - Vaclav Kotesovec, May 30 2021

More terms from Michel Marcus, Jul 15 2018

A316350 Positive integers x that are x/log(x) smooth, that is, if a prime p divides x, then p <= x/log(x).

Original entry on oeis.org

1, 2, 4, 6, 8, 9, 12, 15, 16, 18, 20, 24, 25, 27, 28, 30, 32, 35, 36, 40, 42, 44, 45, 48, 49, 50, 52, 54, 55, 56, 60, 63, 64, 65, 66, 70, 72, 75, 77, 78, 80, 81, 84, 85, 88, 90, 91, 95, 96, 98, 99, 100, 102, 104, 105, 108, 110, 112, 114, 115, 117, 119, 120

Offset: 1

Richard Locke Peterson, Jun 29 2018

nonn

This sequence is a monoid under multiplication, since if x and y are terms in the sequence and p < x/log(x), then p < xy/log(xy). However, if a term in the sequence is multiplied by a number outside the sequence, the result need not be in the sequence.

			1 is in the sequence because no primes divide 1, 2 is in the sequence since 2 divides 2 and 2 < 2/log(2) ~ 2.9, but 10 is not in the sequence since 5 divides 10 and 5 is not less than 10/log(10) ~ 4.34.

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A050500.

filter:= n -> is(max(numtheory:-factorset(n))Robert Israel, Oct 21 2021

ok[n_] := AllTrue[First /@ FactorInteger[n], # Log[n] <= n &]; Select[ Range[120], ok] (* Giovanni Resta, Jun 30 2018 *)

isok(n) = my(f=factor(n)); for (k=1, #f~, if (f[k,1] >= n/log(n), return(0))); return (1); \\ Michel Marcus, Jul 02 2018

A304661 Numbers n that are log_2(n-1)-smooth, i.e., such that all the prime factors of n are less than log_2(n).

Original entry on oeis.org

1, 8, 9, 12, 16, 18, 24, 27, 32, 36, 40, 45, 48, 50, 54, 60, 64, 72, 75, 80, 81, 90, 96, 100, 108, 120, 125, 128, 135, 140, 144, 147, 150, 160, 162, 168, 175, 180, 189, 192, 196, 200, 210, 216, 224, 225, 240, 243, 245, 250, 252, 256, 270, 280, 288, 294, 300

Offset: 1

Richard Locke Peterson, May 16 2018

nonn

The sequence is a monoid since it contains 1 and is closed under multiplication, since if m and n are terms, then any prime dividing m or n must be less than log base 2 of m*n. Density: 27% of the numbers from 1 to 64 are terms. From 2^120 +1 to 2^120+64, 0% are terms. However, it is an infinite sequence, since 2^n is always a term, for n>2.

These numbers are analogous to numbers that are "sqrt(n-1)-smooth" (see A063539).

			40 = 2^3*5 is a term because 2 and 5 are both less than log_2(40).
63 = 9*7 is not a term since 7 is greater than log_2(63).
1 is vacuously a term since it has no prime factors.

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

Cf. A063539.

a:= proc(n) option remember; local k; for k from 1+a(n-1) while {}<>
      select(x-> is(x>=log[2](k)), numtheory[factorset](k)) do od; k
    end: a(1):=1:
seq(a(n), n=1..100);  # Alois P. Heinz, May 18 2018

Join[{1},Select[Range[300],FactorInteger[#][[-1,1]]Harvey P. Dale, Sep 04 2018 *)

isok(n) = my(f=factor(n)[,1], z = log(n)/log(2)); #select(x->(x >= z), f) == 0; \\ Michel Marcus, Jun 01 2018

A291125 "Doubly A289484" numbers: numbers with prime factorization p1^e1 * p2^e2 * ... * pk^ek such that there exist i < j < k with p1^e1 * p2^e2 * ... pi^ei > p(i+1) and p1^e1 * p2^e2 * ... pj^ej > p(j+1).

Original entry on oeis.org

60, 84, 120, 132, 168, 180, 210, 240, 252, 264, 280, 300, 312, 315, 330, 336, 360, 390, 396, 408, 420, 440, 456, 468, 480, 495, 504, 510, 520, 528, 540, 552, 560, 570, 585, 588, 600, 612, 616, 624, 630, 660, 672, 680, 684, 690, 693, 720, 728, 756, 760, 765, 770, 780

Offset: 1

Richard Locke Peterson, Aug 17 2017

nonn

These form a subsemigroup and a subsequence of the sequence A289484.

Density: Only 4.3% of the integers between 1 and 400 are doubly A289484.divisible by at least 3 primes. If a term in the sequence is squarefree, it must be divisible by at least 4 primes. If a number n is in the sequence, then every multiple is also in it. Using Wolfram Alpha, about 48% of the integers between 10^40+1 to 10^40+62 were found to be doubly A289484.

			60=2^2*3*5 is a term because 2^2 > 3 and 2^2*3 > 5.
315=3^2*5*7 is a term because 3^2 > 5 and 3^2*5 > 7.

Cf. A289484.

isA291125 := proc(n)
    local pset,p,pprodidx,pprod,nu,falls ;
    pset := sort(convert(numtheory[factorset](n),list)) ;
    pprod := 1;
    falls := 0 ;
    for pprodidx from 1 to nops(pset)-1 do
        p := pset[pprodidx] ;
        nu := padic[ordp](n,p) ;
        pprod := pprod*p^nu ;
        if pprod > pset[pprodidx+1] then
            falls := falls+1 ;
            if falls >= 2 then
                return true;
            end if;
        end if;
    end do:
    return false ;
end proc:
for n from 1 to 3000 do
    if isA291125(n) then
        printf("%d,",n) ;
    end if;
end do: # R. J. Mathar, Oct 20 2017

is(n,f=factor(n))=my(p=1,t,s); for(i=1,#f~, t=f[i,1]^f[i,2]; if(p>t,s++); p*=t); s>1 \\ Charles R Greathouse IV, Jun 10 2020

New name from Charles R Greathouse IV, Jun 11 2020

A291046 Minimal multiplicative semigroup of numbers n > 1 such that in the prime factorization of n an initial product of primes is greater than a later prime in the factorization.

Original entry on oeis.org

30, 60, 70, 90, 105, 120, 140, 150, 154, 165, 180, 182, 195, 210, 231, 240, 270, 273, 280, 286, 300, 308, 315, 330, 350, 357, 360, 364, 374, 385, 390, 399, 418, 420, 429, 442, 450, 455, 462, 480, 490, 494, 495, 510, 525, 540, 546, 560, 561, 570, 572, 585, 595, 598, 600, 616, 627

Offset: 1

Richard Locke Peterson, Aug 16 2017

nonn

Definition: Let a number n>1 have prime factorization n=p1^e1*...*pi^ei*..*pm^em, with the primes written in ascending order and the ei>0. If an initial product p1*..*pi is greater than some later prime p(i+1), then n is in the sequence. The definition contains a more restrictive requirement than A289484 does, so it is a proper subsemigroup of A289484.  It can be seen that if s and t are in the sequence, the so is s*t. More strongly, if n is in the sequence, so is every multiple of n. Any number in it is divisible by at least 3 primes, although that is not a sufficient condition.
Differs from A212666 first at a(93), because 930=2*3*5*31 is in this sequence but not in A212666. - R. J. Mathar, Sep 02 2018
Numbers whose squarefree kernel (A007947) is in A164596. - Peter Munn, Feb 05 2024

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A007947, A164596, A212666, A289484.

filter:= proc(n) local S,p,i;
  S:= sort(convert(numtheory:-factorset(n),list));
  p:= 1;
  for i from 1 to nops(S)-1 do
    p:= p*S[i];
    if p > S[i+1] then return true fi;
  od;
  false
end proc:
select(filter, [$1..1000]); # Robert Israel, Aug 26 2018

A291045 Numbers with prime factorization such that the cube of a lesser prime in the factorization is greater than the square of a greater prime in the factorization.

Original entry on oeis.org

15, 30, 35, 45, 55, 60, 70, 75, 77, 90, 91, 105, 110, 119, 120, 135, 140, 143, 150, 154, 165, 175, 180, 182, 187, 195, 209, 210, 220, 221, 225, 231, 238, 240, 245, 247, 253, 255, 270, 273, 275, 280, 285, 286, 299, 300, 308, 315, 319, 323, 330, 341, 345, 350, 357, 360, 364, 374, 375, 377

Offset: 1

Richard Locke Peterson, Aug 16 2017

nonn

Definition rephrased: if n is a number with prime divisors p and q with p < q but p^3 > q^2, then n will be in the sequence, otherwise, not.

Sequence is a superclosed semigroup; that is, if s is in the sequence and x is any number, then x*s is in the sequence: if s in the sequence, there are primes p,q dividing s with p < q, p^3 > q^2, so p and q would also divide x*s.

			6 = 2*3 is not in the sequence since 2^3 < 3^2.
15 = 3*5 is in the sequence because 3^3 > 5^2.

Cf. A289484.

isA291045 := proc(n)
    local pdivs,i,j;
    pdivs := sort(convert(numtheory[factorset](n),list)) ;
    for i from 1 to nops(pdivs)-1 do
    for j from i+1 to nops(pdivs) do
        if op(i,pdivs)^3 > op(j,pdivs)^2 then
            return true;
        end if;
    end do:
    end do:
    false;
end proc:
for n from 1 to 400 do
    if isA291045(n) then
        printf("%d,",n) ;
    end if;
end do: # R. J. Mathar, Sep 04 2017

Select[Range@ 400, AnyTrue[Partition[FactorInteger[#][[All, 1]], 2, 1], #1^3 > #2^2 & @@ # &] &] (* Michael De Vlieger, Aug 17 2017 *)

A290965 Let n = p1^e1...pj^ej...pm^em be the prime factorization of n > 1, with the primes in increasing order and ej > 0. If for some j < m the sum p1^2 + ... + pj^2 > p(j+1), then n is in the sequence.

Original entry on oeis.org

6, 12, 15, 18, 21, 24, 30, 35, 36, 42, 45, 48, 54, 55, 60, 63, 65, 66, 70, 72, 75, 77, 78, 84, 85, 90, 91, 95, 96, 102, 105, 108, 110, 114, 115, 119, 120, 126, 130, 132, 133, 135, 138, 140, 143, 144, 147, 150, 154, 156, 161, 162, 165, 168, 170, 174, 175, 180, 182, 186, 187, 189, 190, 192, 195, 198, 203

Offset: 1

Richard Locke Peterson, Aug 15 2017

nonn

Sequence is a semigroup, since it is closed under multiplication, an associative operation--in fact, it is provably superclosed, i.e., a product of a term in sequence and an arbitrary number is a term in the sequence since the preexisting primes will still be in the new number.
Density: There are 28 terms in the sequence less than 100. Using WolframAlpha, 72% of numbers from 10^20 + 1 through 10^20 + 50 were found to be in the sequence.
Other facts: No primes or prime powers are in the sequence.
Related sequences: Some other sequences that are superclosed semigroups are the counting numbers, the numbers that are not squarefree, and the numbers with initial product in factorization greater than a later prime in the factorization. (See crossrefs.)

			6 = 2*3 is a term since 2^2 > 3.
1095 = 3*5*73 is a term because 3^2 > 5.
10, 20, and 100 are not terms since 2^2 < 5.
66 = 2*3*11 and 78 = 2*3*13 are terms since 2^2 + 3^2 > 11 and 2^2 + 3^2 = 13.
975560 = 2^3*5*29^3 is a term since 2^2 + 5^2 = 29.

Cf. A000027, A013929, A289484.

Select[Range@ 203, AnyTrue[Partition[FactorInteger[#][[All, 1]], 2, 1], #1^2 > #2 & @@ # &] &] (* Michael De Vlieger, Aug 17 2017 *)

cp's OEIS Frontend

User: Richard Locke Peterson

A333468 Length of the largest disjoint cycle of the permutation that results from the composition of first n circular shifts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A326119 a(n) is the absolute value of the alternating sum of the first n increasing perfect powers (A001597): 1, 1-4, 1-4+8, 1-4+8-9, ...

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

A318296 Number of conjugacy classes of the Sylow 2-subgroup of the alternating group on n letters.

Views

Author

Keywords

Comments

Crossrefs

Formula

A316353 Number of partitions of positive integer n such that all parts are less than the square root of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A316350 Positive integers x that are x/log(x) smooth, that is, if a prime p divides x, then p <= x/log(x).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A304661 Numbers n that are log_2(n-1)-smooth, i.e., such that all the prime factors of n are less than log_2(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A291125 "Doubly A289484" numbers: numbers with prime factorization p1^e1 * p2^e2 * ... * pk^ek such that there exist i < j < k with p1^e1 * p2^e2 * ... pi^ei > p(i+1) and p1^e1 * p2^e2 * ... pj^ej > p(j+1).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

PARI

Extensions

A290965 Let n = p1^e1...pj^ej...pm^em be the prime factorization of n > 1, with the primes in increasing order and ej > 0. If for some j < m the sum p1^2 + ... + pj^2 > p(j+1), then n is in the sequence.