| Displaying 1-3 of 3 results found.
page
1
a(n) = ceiling((9*(9/4)^n - 4) / 5).
+10
6
1, 4, 9, 20, 46, 103, 233, 525, 1182, 2660, 5985, 13467, 30301, 68178, 153401, 345152, 776591, 1747331, 3931496, 8845866, 19903198, 44782196, 100759940, 226709866, 510097200, 1147718700, 2582367076, 5810325920, 13073233321, 29414774973
COMMENTS
The old definition was "Tokuda's good set of increments for Shell sort", but that seems to be false.
Adding 0, -1, -1, -1, ... to the terms gives A361506. For another version see A361507.
REFERENCES
N. Tokuda, An Improved Shellsort, IFIP Transactions, A-12 (1992) 449-457.
LINKS
Marcin Ciura, Best Increments for the Average Case of Shellsort, in R. Freivalds, (ed.), Fundamentals of Computation Theory: 13th International Symposium, FCT 2001, Riga, Latvia, August 2001, Lecture Notes in Computer Science, vol. 2138, Springer, pp. 106-117.
a(0) = 1; thereafter a(n) = floor((9/4)*a(n-1)) + 1.
+10
4
1, 3, 7, 16, 37, 84, 190, 428, 964, 2170, 4883, 10987, 24721, 55623, 125152, 281593, 633585, 1425567, 3207526, 7216934, 16238102, 36535730, 82205393, 184962135, 416164804, 936370810, 2106834323, 4740377227, 10665848761, 23998159713, 53995859355, 121490683549, 273354037986, 615046585469, 1383854817306, 3113673338939
REFERENCES
N. Tokuda, An efficient Shell's method of sorting by generalized scheme, Department of Computer Science, Utunomiya University, 1989; 10 pages plus 9 unnumbered pages of tables and charts.
MATHEMATICA
NestList[Floor[9/4#]+1&, 1, 50] (* Paolo Xausa, Dec 02 2023 *)
Basic numbers used in Sedgewick-Incerpi upper bound for shell sort.
+10
3
1, 3, 7, 16, 41, 101, 247, 613, 1529, 3821, 9539, 23843, 59611, 149015, 372539, 931327, 2328307, 5820767, 14551919, 36379789, 90949471, 227373677, 568434193, 1421085473, 3552713687, 8881784201, 22204460497, 55511151233, 138777878081, 346944695197, 867361737989
REFERENCES
D. E. Knuth, The Art of Computer Programming, Vol. 3, Sorting and Searching, 2nd ed, section 5.2.1, p. 91.
FORMULA
a(n) is the smallest number >= 2.5^n that is relatively prime to all previous terms in the sequence.
EXAMPLE
2.5^4 = 39.0625, and 41 is the next integer that is relatively prime to 1, 3, 7 and 16.
MAPLE
a:= proc(n) option remember; local l, m;
l:= [seq(a(i), i=1..n-1)];
for m from ceil((5/2)^n) while ormap(x-> igcd(m, x)>1, l) do od; m
end:
MATHEMATICA
With[{prev = A036567 /@ Range[q - 1]}, Block[{n = Ceiling[(5/2)^q]},
While[Nand @@ ((# == 1 &) /@ GCD[prev, n]), n++];
PROG
(PARI) a036567(m)={my(v=vector(m)); for(n=1, m, my(b=ceil((5/2)^n)); for(j=b, oo, my(g=1); for(k=1, n-1, if(gcd(j, v[k])>1, g=0; break)); if(g, v[n]=j; break))); v};
CROSSREFS
Cf. A003462, A033622, A036561, A036562, A036564, A036566, A036567, A036569, A055875, A055876, A102549, A108870, A112262, A112263, A154393, A204772, A205669, A205670, A361506, A361507.
EXTENSIONS
Better description and more terms from Jud McCranie, Jan 05 2001
Search completed in 0.005 seconds
| 