login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Search: keyword:new
Displaying 1-10 of 376 results found. page 1 2 3 4 5 6 7 8 9 10 ... 38
     Sort: relevance | references | number | modified | created      Format: long | short | data
A374912 Primes p sush that (p - 1)^p == p (mod 2*p - 1). +0
0
3, 7, 19, 31, 79, 139, 199, 211, 271, 307, 331, 367, 379, 439, 499, 547, 607, 619, 691, 727, 811, 967, 1171, 1279, 1399, 1459, 1531, 1627, 1759, 1867, 2011, 2131, 2179, 2311, 2467, 2539, 2551, 2707, 2719, 2791, 2851, 3019, 3067, 3187, 3319, 3331, 3391, 3499, 3607, 3739, 3967 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,1
LINKS
PROG
(Magma) [p: p in PrimesUpTo(10^4) | (p-1)^p mod (2*p-1) eq p];
(PARI) list(lim)=my(v=List([3])); forprimestep(p=7, lim\1, 12, if(Mod(p-1, 2*p-1)^p==p, listput(v, p))); Vec(v) \\ Charles R Greathouse IV, Jul 23 2024
CROSSREFS
Aside from the first term, a subsequence of A068229.
KEYWORD
nonn,new
AUTHOR
STATUS
approved
A374305 Number of growing self-avoiding walks of length n on a half-infinite strip of height 7 with a trapped endpoint. +0
0
2, 2, 8, 11, 34, 70, 180, 423, 1035, 2557, 6106, 15039, 35538, 85561, 201870, 478444, 1129498, 2654505, 6270807, 14679261, 34662653, 81011176, 191059001, 446245461, 1050699473, 2453328994, 5766594972, 13462400943, 31595520207, 73752506984, 172876421034 (list; graph; refs; listen; history; text; internal format)
OFFSET
5,1
COMMENTS
A growing self-avoiding walk (GSAW) is a walk on a graph that is directed, does not visit the same vertex twice, and for which all neighbors of the endpoint are part of the walk, i.e., the endpoint is trapped. This sequence is about GSAWs on the grid graph of integer points (x,y) where x >= 0 and y is in {0,1,2,3,4,5,6}. The GSAW must start at the point (0,0). The length of a GSAW is the number of edges.
LINKS
Jay Pantone, generating function
FORMULA
See Links section for generating function.
EXAMPLE
The a(5) = 2 walks are:
> * * * * * *
>
> * * * * * *
>
> * * * * * *
>
> * * * * * *
>
> *--* * * * *
> | |
> * * * *--*--*
> | | |
> *--* * * *--*
CROSSREFS
KEYWORD
nonn,new
AUTHOR
Jay Pantone, Jul 22 2024
STATUS
approved
A374304 Number of growing self-avoiding walks with displacement n on a half-infinite strip of height 6 with a trapped endpoint. +0
0
23, 629, 15134, 323031, 6428665, 122523673, 2267420832, 41081096139, 732520397439, 12900298930153, 224940605616826, 3890634712091201, 66843522591221500, 1141958198925483582, 19416047904038468727, 328765736871514344297, 5547125910154291613320 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,1
COMMENTS
A growing self-avoiding walk (GSAW) is a walk on a graph that is directed, does not visit the same vertex twice, and for which all neighbors of the endpoint are part of the walk, i.e., the endpoint is trapped. This sequence is about GSAWs on the grid graph of integer points (x,y) where x >= 0 and y is in {0,1,2,3,4,5}. The GSAW must start at the point (0,0). The displacement of a GSAW is the difference between the largest and smallext x-values that it reaches.
LINKS
Jay Pantone, generating function
FORMULA
See Links section for generating function.
EXAMPLE
Five of the a(1) = 23 walks are:
*--* * * * * * * * * * * *--* *
| | | |
* * * *--* * *--* * * * * * * *
| | | | | | | |
* * * * * * * * * * * * * * *
| | | | | |
*--* * * * * *--* * *--* * * * *
| | | | | | |
* * * *--* * *--* * * * * * * *
| | | | |
* * * * * * *--* * *--* * *--* *
CROSSREFS
KEYWORD
nonn,new
AUTHOR
Jay Pantone, Jul 22 2024
STATUS
approved
A374630 Sum of leaders of weakly increasing runs in the n-th composition in standard order. +0
0
0, 1, 2, 1, 3, 3, 1, 1, 4, 4, 2, 3, 1, 2, 1, 1, 5, 5, 5, 4, 2, 3, 3, 3, 1, 2, 1, 2, 1, 2, 1, 1, 6, 6, 6, 5, 3, 6, 4, 4, 2, 3, 2, 3, 3, 4, 3, 3, 1, 2, 3, 2, 1, 2, 2, 2, 1, 2, 1, 2, 1, 2, 1, 1, 7, 7, 7, 6, 7, 7, 5, 5, 3, 4, 5, 6, 4, 5, 4, 4, 2, 3, 4, 3, 2, 3, 3 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,3
COMMENTS
The leaders of weakly increasing runs in a sequence are obtained by splitting it into maximal weakly increasing subsequences and taking the first term of each.
The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.
LINKS
EXAMPLE
The maximal weakly increasing subsequences of the 1234567th composition in standard order are ((3),(2),(1,2,2),(1,2,5),(1,1,1)), so a(1234567) = 8.
MATHEMATICA
stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n, 2]], 1], 0]]//Reverse;
Table[Total[First/@Split[stc[n], LessEqual]], {n, 0, 100}]
CROSSREFS
For length instead of sum we have A124766.
For leaders of constant runs we have A373953, excess A373954.
For leaders of anti-runs we have A374516.
Row-sums of A374629.
Counting compositions by this statistic gives A374637.
For leaders of strictly increasing runs we have A374684.
For leaders of weakly decreasing runs we have A374741.
For leaders of strictly decreasing runs we have A374758
A011782 counts compositions.
A238130, A238279, A333755 count compositions by number of runs.
A335456 counts patterns matched by compositions.
A373949 counts compositions by run-compressed sum, opposite A373951.
All of the following pertain to compositions in standard order:
- Ones are counted by A000120.
- Sum is A029837 (or sometimes A070939).
- Listed by A066099.
- Length is A070939.
- Number of adjacent equal pairs is A124762, unequal A333382.
- Number of max runs: A124765, A124766, A124767, A124768, A124769, A333381.
- Ranks of strict compositions are A233564, counted by A032020.
- Constant compositions are ranked by A272919.
- Ranks of anti-run compositions are A333489, counted by A003242.
- Run-length transform is A333627.
- Run-compression transform is A373948.
KEYWORD
nonn,new
AUTHOR
Gus Wiseman, Jul 20 2024
STATUS
approved
A374633 Numbers k such that the leaders of weakly increasing runs in the k-th composition in standard order (A066099) are identical. +0
0
0, 1, 2, 3, 4, 6, 7, 8, 10, 12, 13, 14, 15, 16, 20, 24, 25, 26, 27, 28, 29, 30, 31, 32, 36, 40, 42, 48, 49, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 72, 80, 82, 84, 96, 97, 99, 100, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 115 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,3
COMMENTS
The leaders of weakly increasing runs in a sequence are obtained by splitting it into maximal weakly increasing subsequences and taking the first term of each.
The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.
LINKS
EXAMPLE
The maximal weakly increasing subsequences of the 26165th composition in standard order are ((1,3),(1,4),(1,2,2),(1)), with leaders (1,1,1,1), so 26165 is in the sequence.
The sequence together with the corresponding compositions begins:
0: ()
1: (1)
2: (2)
3: (1,1)
4: (3)
6: (1,2)
7: (1,1,1)
8: (4)
10: (2,2)
12: (1,3)
13: (1,2,1)
14: (1,1,2)
15: (1,1,1,1)
16: (5)
20: (2,3)
24: (1,4)
25: (1,3,1)
26: (1,2,2)
27: (1,2,1,1)
MATHEMATICA
stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n, 2]], 1], 0]]//Reverse;
Select[Range[0, 100], SameQ@@First/@Split[stc[#], LessEqual]&]
CROSSREFS
For strictly decreasing leaders we appear to have A188920.
For weakly decreasing leaders we appear to have A189076.
Other types of runs: A272919 (counted by A000005), A374519 (counted by A374517), A374685 (counted by A374686), A374744 (counted by A374742), A374759 (counted by A374760).
Positions of constant rows in A374629 (which has sums A374630).
Compositions of this type are counted by A374631.
For strictly increasing leaders see A374634.
For all different leaders we have A374768, counted by A374632.
A011782 counts compositions.
A238130, A238279, A333755 count compositions by number of runs.
A374637 counts compositions by sum of leaders of weakly increasing runs.
All of the following pertain to compositions in standard order:
- Ones are counted by A000120.
- Sum is A029837 (or sometimes A070939).
- Parts are listed by A066099.
- Length is A070939.
- Adjacent equal pairs are counted by A124762, unequal A333382.
- Number of max runs: A124765, A124766, A124767, A124768, A124769, A333381.
- Ranks of anti-run compositions are A333489, counted by A003242.
- Run-length transform is A333627.
- Run-compression transform is A373948, sum A373953, excess A373954.
- Ranks of contiguous compositions are A374249, counted by A274174.
KEYWORD
nonn,new
AUTHOR
Gus Wiseman, Jul 21 2024
STATUS
approved
A374768 Numbers k such that the leaders of weakly increasing runs in the k-th composition in standard order (A066099) are distinct. +0
0
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 26, 28, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 46, 47, 48, 50, 52, 56, 58, 60, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 78, 79, 80, 81 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,3
COMMENTS
First differs from A335467 in having 166, corresponding to the composition (2,3,1,2).
The leaders of weakly increasing runs in a sequence are obtained by splitting it into maximal weakly increasing subsequences and taking the first term of each.
The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.
LINKS
EXAMPLE
The 4444th composition in standard order is (4,2,2,1,1,3), with weakly increasing runs ((4),(2,2),(1,1,3)), with leaders (4,2,1), so 4444 is in the sequence.
MATHEMATICA
stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n, 2]], 1], 0]]//Reverse;
Select[Range[0, 166], UnsameQ@@First/@Split[stc[#], LessEqual]&]
CROSSREFS
These are the positions of strict rows in A374629 (which has sums A374630).
Compositions of this type are counted by A374632, increasing A374634.
Identical instead of distinct leaders are A374633, counted by A374631.
For leaders of anti-runs we have A374638, counted by A374518.
For leaders of strictly increasing runs we have A374698, counted by A374687.
For leaders of weakly decreasing runs we have A374701, counted by A374743.
For leaders of strictly decreasing runs we have A374767, counted by A374761.
A011782 counts compositions.
A238130, A238279, A333755 count compositions by number of runs.
All of the following pertain to compositions in standard order:
- Ones are counted by A000120.
- Sum is A029837 (or sometimes A070939).
- Parts are listed by A066099.
- Length is A070939.
- Adjacent equal pairs are counted by A124762, unequal A333382.
- Number of max runs: A124765, A124766, A124767, A124768, A124769, A333381.
- Ranks of strict compositions are A233564.
- Ranks of constant compositions are A272919.
- Ranks of anti-run compositions are A333489, counted by A003242.
- Run-length transform is A333627.
- Run-compression transform is A373948, sum A373953, excess A373954.
KEYWORD
nonn,new
AUTHOR
Gus Wiseman, Jul 19 2024
STATUS
approved
A374811 Numerator of the expected height of a random binary search tree (BST) with n elements. +0
0
-1, 0, 1, 5, 7, 14, 49, 1156, 2531, 2461, 5263, 23231, 48857, 142327, 161366, 677983151, 701098187, 49162215523, 56895744916, 97659246406291, 28593399072431, 21502630803250973, 26851741349945933, 246602936364321931, 1508124176077531039, 10968493811640186469 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,4
COMMENTS
Here we're using the conventional definition of BST height, which is path length from the root to the node (the height of an empty tree is -1), as compared to A195582 which has the height one greater.
LINKS
FORMULA
a(n) = numerator(A195582(n)/A195583(n) - 1).
a(n) = A195582(n) - A195583(n). - Alois P. Heinz, Jul 20 2024
MAPLE
b:= proc(n, k) option remember;
if n=0 then 1
elif n=1 then `if`(k>0, 1, 0)
else add(binomial(n-1, r-1) *b(r-1, k-1) *b(n-r, k-1), r=1..n)
fi
end:
T:= (n, k)-> b(n, k)-`if`(k>0, b(n, k-1), 0):
a:= n-> add(T(n, k)*k, k=0..n)/n!:
seq(numer(a(n)-1), n=0..30);
MATHEMATICA
[n_, k_] := b[n, k] = If[n==0, 1, If[n==1, If[k>0, 1, 0], Sum[Binomial[n - 1, r-1]*b[r-1, k-1]*b[n-r, k-1], {r, 1, n}]]]; T[n_, k_] := b[n, k] - If[ k>0, b[n, k-1], 0]; a[n_] := Sum[T[n, k]*k, {k, 0, n}]/n!; Table[ Numerator[a[n]-1], {n, 0, 30}]
CROSSREFS
Denominators: A195583.
Cf. A195582.
KEYWORD
sign,frac,new
AUTHOR
Melissa O'Neill, Jul 20 2024
STATUS
approved
A373769 The smallest number of conjugacy classes of a group of order 2^n. +0
0
2, 4, 5, 7, 11, 13, 14, 19, 26, 28, 29, 34, 35, 37 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,1
LINKS
E. A. Bertram, New lower bounds for the number of conjugacy classes in finite nilpotent groups, Int. J. Group Theory 11 (2022), no. 2, 109-119.
N. Boston and J. L. Walker, 2-groups with few conjugacy classes, Proc. Edinburgh Math. Soc.(2) 43 (2000), no. 1, 211-217.
KEYWORD
nonn,more,new
AUTHOR
Thomas Wilde, Jun 18 2024
STATUS
approved
A374260 Decimal expansion of the Euclidean length of the shortest circuit covering all the vertices of the cube [0,1]^3. +0
0
1, 5, 3, 8, 2, 0, 7, 5, 1, 2, 1, 3, 8, 4, 4, 7, 3, 4, 9, 7, 1, 1, 4, 9, 6, 4, 7, 9, 4, 6, 2, 8, 9, 9, 4, 0, 9, 8, 7, 3, 9, 0, 7, 5, 8, 6, 9, 0, 8, 4, 4, 5, 0, 7, 3, 0, 8, 2, 6, 7, 5, 0, 8, 8, 8, 3, 4, 9, 5, 4, 7, 2, 6, 8, 5, 3, 2, 8, 3, 4, 3, 5, 8, 9, 3, 3, 8 (list; constant; graph; refs; listen; history; text; internal format)
OFFSET
2,2
COMMENTS
It has been proved that it is not possible to join the 8 vertices of a cube with a polygonal chain that has fewer than 6 edges (see Links, Optimal cycles enclosing all the nodes of a k-dimensional hypercube, Theorem 2.2). Thus, any circuit of 6 line segments covering all the vertices of a cube has the minimum link-length (by definition).
Here we consider the additional constraint of minimizing the total (Euclidean) length of the minimum-link circuit (which consists of exactly 6 line segments connected at their endpoints) that joins all the vertices of the cube [0,1] X [0,1] X [0,1].
Let x := (1/2)*sqrt((2/3)^(2/3)*((9+sqrt(177)))^(1/3) - 4*(2/(27+3*sqrt(177)))^(1/3)) + (1/2)*sqrt(4*(2/(27+3*sqrt(177)))^(1/3) - (2/3)^(2/3)*(9+sqrt(177))^(1/3) + 4*sqrt(2/((2/3)^(2/3)*(9+sqrt(177))^(1/3) - 4*(2/(27+3*sqrt(177)))^(1/3)))) = 1.597920933550032074764705350780465558827883608091828573735862154752648..., and then let c := 1+(x+2+sqrt(2))/(2*sqrt(2)*(x+sqrt(2))).
A solution to the above-stated problem is provided by the 6-link circuit (1/2, 1/2, 1+x/sqrt(2))-(c,c,0)-(-c,-c,0)-(1/2,1/2, 1+x/sqrt(2))-(-c,c,0)-(c,-c,0)-(1/2, 1/2, 1+x/sqrt(2)).
The total (Euclidean) length of the mentioned circuit is given by 4*((2+sqrt(2)*x)/2)*(1/x+sqrt(1+1/x^2)) = which is about 11.105251123 and this value cannot be beaten by any other 6-link circuit covering all the vertices belonging to the set {0,1} X {0,1} X {0,1}. This result follows by symmetry from the optimal polygonal chain described in the comments of A373537.
LINKS
Roberto Rinaldi and Marco Ripà, Optimal cycles enclosing all the nodes of a k-dimensional hypercube, arXiv:2212.11216 [math.CO], 2022.
FORMULA
Equals 2*(2+sqrt(2)*x)*(1/x+sqrt(1+1/x^2)), where x = (1/2)*sqrt((2/3)^(2/3)*((9+sqrt(177)))^(1/3) - 4*(2/(27+3*sqrt(177)))^(1/3)) + (1/2)*sqrt(4*(2/(27+3*sqrt(177)))^(1/3) - (2/3)^(2/3)*(9+sqrt(177))^(1/3) + 4*sqrt(2/((2/3)^(2/3)*(9+sqrt(177))^(1/3) - 4*(2/(27+3*sqrt(177)))^(1/3)))) = 1.59792093355003207476470...
EXAMPLE
15.382075121384473497114964794628994098739075869...
PROG
(PARI) my(x=solve(x=1.5, 1.7, 4-8*x^2-4*x^4+x^8)); 2*(sqrt(1 + 1/x^2) + 1/x)*(2 + x*sqrt(2)) \\ Hugo Pfoertner, Jul 01 2024
CROSSREFS
KEYWORD
nonn,cons,new
AUTHOR
Marco Ripà, Jul 01 2024
STATUS
approved
A374224 Integer part of the total Euclidean length of the shortest minimum-link polygonal chains joining all the nodes of the grid {0,1,...,n-1} X {0,1,...,n-1}. +0
0
0, 3, 12, 20, 28, 40, 53, 68, 85, 104, 125, 148, 173, 200, 229, 260, 293, 328, 365, 404, 445, 488, 533, 580, 629, 680, 733, 788, 845, 904, 965, 1028, 1093, 1160, 1229, 1300, 1373, 1448, 1525, 1604, 1685, 1768, 1853, 1940, 2029, 2120, 2213, 2308, 2405, 2504 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,2
COMMENTS
This sequence describes the optimal solution of the 2D generalization of the well-known nine dots problem, published in Loyd’s Cyclopedia of Puzzles (1914), p. 301.
Since Solomon Golomb constructively proved that, for any n >= 3, the minimum-link polygonal chain covering a given {0,1,...,n-1} X {0,1,...,n-1} grid consists of (exactly) 2*(n - 1) line segments, we only need to find the shortest trail satisfying the constraint above.
In detail, if n = 2, the trivial spanning path (0,1)-(0,0)-(1,0)-(1,1) is optimal. If n = 3, we have the classic solution of the nine dots problem (0,1)-(0,3)-(3,0)-(0,0)-(2,2). Now, if n > 3, a valid upper bound is given by n^2 + 5*sqrt(2) - 3, but it is possible to improve this solution for the n = 5 case by providing the trail.
(2,3)-(4,3)-(1,0)-(1,3)-(4,0)-(0,0)-(0,4)-(4,4)-(4,1), whose total Euclidean length is 20 + 6*sqrt(2). In the end, assuming n > 5, we can recycle the mentioned solution, then extend the last line segment to reach (4,-1), and finally apply the square spiral pattern to the (extended) ending segment of the {0,1,...,n-1} X {0,1,...,n-1} grid solution in order to get the solution for the {0,1,...,n} X {0,1,...,n} case, joining 2*n + 1 more points by spending two additional line segments having a combined length of 2*n (and this is an iterative strategy which is optimal for any n > 5).
LINKS
Marco Ripà, Shortest polygonal chains covering each planar square grid, arXiv:2207.08708 [math.CO], 2022. See pp. 11-13.
FORMULA
a(1) = 1, a(2) = 3, a(3) = floor(5*(1+sqrt(2))) = 12, a(5) = floor(20 + 6*sqrt(2)) = 28, and a(n) = floor(n^2 + 5*sqrt(2)) - 3 iff n = 4 or n >= 6.
For n > 5, a(n) = n^2 + 4.
G.f.: x^2*(3 + 3*x - 7*x^2 + x^3 + 4*x^4 - 3*x^5 + x^6)/(1 - x)^3. - Stefano Spezia, Jul 02 2024
EXAMPLE
a(2) = 3 since we can join the points {0,1}^2 with a spanning path consisting of 3 line segments having a total Euclidean length of 2^2 - 1.
MATHEMATICA
Join[{0, 3, 12, 20, 28} Table[Floor[n^2 + 5*Sqrt[2]] - 3 , {n, 6, 50}]]
CROSSREFS
KEYWORD
nonn,easy,new
AUTHOR
Marco Ripà, Jun 30 2024
STATUS
approved
page 1 2 3 4 5 6 7 8 9 10 ... 38

Search completed in 0.129 seconds

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 23 09:01 EDT 2024. Contains 374547 sequences. (Running on oeis4.)