Search: keyword:new
|
|
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
|
|
|
FORMULA
|
See Links section for generating function.
|
|
EXAMPLE
|
The a(5) = 2 walks are:
> * * * * * *
>
> * * * * * *
>
> * * * * * *
>
> * * * * * *
>
> *--* * * * *
> | |
> * * * *--*--*
> | | |
> *--* * * *--*
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,new
|
|
AUTHOR
|
|
|
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
|
|
|
FORMULA
|
See Links section for generating function.
|
|
EXAMPLE
|
Five of the a(1) = 23 walks are:
*--* * * * * * * * * * * *--* *
| | | |
* * * *--* * *--* * * * * * * *
| | | | | | | |
* * * * * * * * * * * * * * *
| | | | | |
*--* * * * * *--* * *--* * * * *
| | | | | | |
* * * *--* * *--* * * * * * * *
| | | | |
* * * * * * *--* * *--* * *--* *
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,new
|
|
AUTHOR
|
|
|
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 anti-runs we have A374516.
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
A335456 counts patterns matched by compositions.
All of the following pertain to compositions in standard order:
- Constant compositions are ranked by A272919.
- Run-compression transform is A373948.
|
|
KEYWORD
|
nonn,new
|
|
AUTHOR
|
|
|
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.
Compositions of this type are counted by A374631.
For strictly increasing leaders see A374634.
A374637 counts compositions by sum of leaders of weakly increasing runs.
All of the following pertain to compositions in standard order:
|
|
KEYWORD
|
nonn,new
|
|
AUTHOR
|
|
|
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).
Identical instead of distinct leaders are A374633, counted by A374631.
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.
All of the following pertain to compositions in standard order:
- Ranks of strict compositions are A233564.
- Ranks of constant compositions are A272919.
Cf. A065120, A188920, A189076, A238343, A333213, A335449, A373949, A274174, A374249, A374635, A374637.
|
|
KEYWORD
|
nonn,new
|
|
AUTHOR
|
|
|
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
|
|
|
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
|
|
|
KEYWORD
|
sign,frac,new
|
|
AUTHOR
|
|
|
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
|
|
|
KEYWORD
|
nonn,more,new
|
|
AUTHOR
|
|
|
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
|
|
|
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
|
|
|
AUTHOR
|
|
|
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
|
|
|
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
|
|
|
STATUS
|
approved
|
|
|
Search completed in 0.129 seconds
|