Search: a099004 -id:a099004
|
| |
|
|
A005228
|
|
Sequence and first differences (A030124) together list all positive numbers exactly once.
(Formerly M2629)
|
|
+10
71
|
|
|
|
1, 3, 7, 12, 18, 26, 35, 45, 56, 69, 83, 98, 114, 131, 150, 170, 191, 213, 236, 260, 285, 312, 340, 369, 399, 430, 462, 495, 529, 565, 602, 640, 679, 719, 760, 802, 845, 889, 935, 982, 1030, 1079, 1129, 1180, 1232, 1285, 1339, 1394, 1451, 1509, 1568, 1628, 1689
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
This is the lexicographically earliest sequence that together with its first differences (A030124) contains every positive integer exactly once.
Hofstadter introduces this sequence in his discussion of Scott Kim's "FIGURE-FIGURE" drawing. - N. J. A. Sloane, May 25 2013
In view of the definition of A075326: start with a(0) = 0, and extend by rule that the next term is the sum of the predecessor and the most recent non-member of the sequence. - Reinhard Zumkeller, Oct 26 2014
|
|
|
REFERENCES
|
E. Angelini, "Jeux de suites", in Dossier Pour La Science, pp. 32-35, Volume 59 (Jeux math'), April/June 2008, Paris.
D. R. Hofstadter, Goedel, Escher, Bach: an Eternal Golden Braid, Random House, 1980, p. 73.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
|
D. R. Hofstadter, Eta-Lore [Cached copy, with permission]
|
|
|
FORMULA
|
a(n) = a(n-1) + c(n-1) for n >= 2, where a(1)=1, a( ) increasing, c( ) = complement of a( ) (c is the sequence A030124).
Let a(n) = this sequence, b(n) = A030124 prefixed by 0. Then b(n) = mex{ a(i), b(i) : 0 <= i < n}, a(n) = a(n-1) + b(n) + 1. (Fraenkel)
a(1) = 1, a(2) = 3; a( ) increasing; for n >= 3, if a(q) = a(n-1)-a(n-2)+1 for some q < n then a(n) = a(n-1) + (a(n-1)-a(n-2)+2), otherwise a(n) = a(n-1) + (a(n-1)-a(n-2)+1). - Albert Neumueller (albert.neu(AT)gmail.com), Jul 29 2006
a(n) = n^2/2 + n^(3/2)/(3*sqrt(2)) + O(n^(5/4)) [proved in Jubin link]. - Benoit Jubin, May 13 2015
|
|
|
EXAMPLE
|
Sequence reads 1 3 7 12 18 26 35 45..., differences are 2 4 5, 6, 8, 9, 10 ... and the point is that every number not in the sequence itself appears among the differences. This property (together with the fact that both the sequence and the sequence of first differences are increasing) defines the sequence!
|
|
|
MAPLE
|
maxn := 5000; h := array(1..5000); h[1] := 1; a := [1]; i := 1; b := []; for n from 2 to 1000 do if h[n] <> 1 then b := [op(b), n]; j := a[i]+n; if j < maxn then a := [op(a), j]; h[j] := 1; i := i+1; fi; fi; od: a; b; # a is A005228, b is A030124.
option remember;
local a, fnd, t ;
if n <= 1 then
op(n+1, [2, 4]) ;
else
for a from procname(n-1)+1 do
fnd := false;
for t from 1 to n+1 do
fnd := true;
break;
end if;
end do:
if not fnd then
return a;
end if;
end do:
end if;
end proc:
option remember;
if n <= 2 then
op(n, [1, 3]) ;
else
end if;
|
|
|
MATHEMATICA
|
a = {1}; d = 2; k = 1; Do[ While[ Position[a, d] != {}, d++ ]; k = k + d; d++; a = Append[a, k], {n, 1, 55} ]; a
(* Second program: *)
(* Program from Larry Morris, Jan 19 2017: *)
d = 3; a = {1, 3, 7, 12, 18}; While[ Length[a = Join[a, a[[-1]] + Accumulate[Range[a[[d]] + 1, a[[++d]] - 1]]]] < 50]; a
(* Comment: This adds as many terms to the sequence as there are numbers in each set of sequential differences. Consequently, the list of numbers it produces may be longer than the limit provided. With the limit of 50 shown, the sequence produced has length 60. *)
|
|
|
PROG
|
(Haskell)
import Data.List (delete)
a005228 n = a005228_list !! (n-1)
a005228_list = 1 : figure 1 [2..] where
figure n (x:xs) = n' : figure n' (delete n' xs) where n' = n + x
(PARI) A005228(n, print_all=0, s=1, used=0)={while(n--, used += 1<<s; print_all & print1(s", "); for(k=s+1, 9e9, bittest(used, k) & next; bittest(used, k-s) & next; used += 1<<(k-s); s=k; break)); s} \\ M. F. Hasler, Feb 05 2013
|
|
|
CROSSREFS
|
The following are a group of related sequences: A005132, A006509, A037257, A037258, A037259, A081145, A093903, A099004, A100707, A129198, A129199, A140778, A225376, A225377, A225378, A225385, A225386, A225387.
Cf. A001651 (analog with sums instead of differences), A121229 (analog with products).
Related recurrences:
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A081145
|
|
a(1)=1; thereafter, a(n) is the least positive integer which has not already occurred and is such that |a(n)-a(n-1)| is different from any |a(k)-a(k-1)| which has already occurred.
|
|
+10
51
|
|
|
|
1, 2, 4, 7, 3, 8, 14, 5, 12, 20, 6, 16, 27, 9, 21, 34, 10, 25, 41, 11, 28, 47, 13, 33, 54, 15, 37, 60, 17, 42, 68, 18, 45, 73, 19, 48, 79, 22, 55, 23, 58, 94, 24, 61, 99, 26, 66, 107, 29, 71, 115, 30, 75, 121, 31, 78, 126, 32, 81, 132, 35, 87, 140, 36, 91, 147, 38, 96, 155, 39
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
The sequence is a permutation of the positive integers. The inverse is A081146.
Similar to A100707, except that when we subtract we use the largest possible k.
The 1977 paper of Slater and Velez proves that this sequence is a permutation of positive integers and conjectures that its absolute difference sequence (see A308007) is also a permutation. If we call this the "Slater-Velez permutation of the first kind", then they also constructed another permutation (the 2nd kind), for which they are able to prove that both the sequence (A129198) and its absolute difference (A129199) are true permutations. - Ferenc Adorjan, Apr 03 2007
The points appear to lie on three straight lines of slopes roughly 0.56, 1.40, 2.24 (click "graph", or see the Wilks link). I checked this for the first 10^6 terms using Allan Wilks's C program. See A308009-A308015 for further information about the three lines. - N. J. A. Sloane, May 14 2019
|
|
|
REFERENCES
|
P. J. Slater and W. Y. Velez, Permutations of the Positive Integers with Restrictions on the Sequence of Differences, II, Pacific Journal of Mathematics, Vol. 82, No. 2, 1979, 527-531.
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
a(4)=7 because the previous term is 4 and the differences |3-4|, |5-4| and |6-4| have already occurred.
After 7 we get 3 as the difference 4 has not occurred earlier. 5 follows 14 as the difference 9 has not occurred earlier.
|
|
|
MATHEMATICA
|
f[s_] := Block[{d = Abs[Rest@s - Most@s], k = 1}, While[ MemberQ[d, Abs[k - Last@s]] || MemberQ[s, k], k++ ]; Append[s, k]]; NestList[s, {1}, 70] (* Robert G. Wilson v, Jun 09 2006 *)
f[s_] := Block[{k = 1, d = Abs[Most@s - Rest@s], l = Last@s}, While[MemberQ[s, k] || MemberQ[d, Abs[l - k]], k++ ]; Append[s, k]]; Nest[f, {1}, 70] (* Robert G. Wilson v, Jun 13 2006 *)
|
|
|
PROG
|
(PARI){SV_p1(n)=local(x, v=6, d=2, j, k); /* Slater-Velez permutation - the first kind (by F. Adorjan)*/ x=vector(n); x[1]=1; x[2]=2; for(i=3, n, j=3; k=1; while(k, if(k=bittest(v, j)||bittest(d, abs(j-x[i-1])), j++, v+=2^j; d+=2^abs(j-x[i-1]); x[i]=j))); return(x)} \\ Ferenc Adorjan, Apr 03 2007
(Python)
A081145_list, l, s, b1, b2 = [1, 2], 2, 3, set(), set([1])
for n in range(3, 10**2):
i = s
while True:
m = abs(i-l)
if not (i in b1 or m in b2):
b1.add(i)
b2.add(m)
l = i
while s in b1:
b1.remove(s)
s += 1
break
(Haskell)
import Data.List (delete)
a081145 n = a081145_list !! (n-1)
a081145_list = 1 : f 1 [2..] [] where
f x vs ws = g vs where
g (y:ys) = if z `elem` ws then g ys else y : f y (delete y vs) (z:ws)
where z = abs (x - y)
|
|
|
CROSSREFS
|
A308172 gives smallest missing numbers.
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A030124
|
|
Complement (and also first differences) of Hofstadter's sequence A005228.
|
|
+10
38
|
|
|
|
2, 4, 5, 6, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25, 27, 28, 29, 30, 31, 32, 33, 34, 36, 37, 38, 39, 40, 41, 42, 43, 44, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 70, 71, 72, 73, 74, 75, 76, 77, 78
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
COMMENTS
|
For any n, all integers k satisfying sum(i=1,n,a(i))+1<k<sum(i=1,n+1,a(i))+1 are in the sequence. E.g., sum(i=1,3,a(i))+1=12, sum(i=1,4,a(i))+1=18, hence 13,14,15,16,17 are in the sequence. - Benoit Cloitre, Apr 01 2002
The asymptotic equivalence a(n) ~ n follows from the fact that the values disallowed in the present sequence because they occur in A005228 are negligible, since A005228 grows much faster than A030124. The next-to-leading term in the formula is calculated from the functional equation F(x) + G(x) = x, suggested by D. Wilson (cf. reference), where F and G are the inverse functions of smooth, increasing approximations f and f' of A005228 and A030124. It seems that higher order corrections calculated from this equation do not agree with the real behavior of a(n). - M. F. Hasler, Jun 04 2008
|
|
|
REFERENCES
|
E. Angelini, "Jeux de suites", in Dossier Pour La Science, pp. 32-35, Volume 59 (Jeux math'), April/June 2008, Paris.
D. R. Hofstadter, "Gödel, Escher, Bach: An Eternal Golden Braid", Basic Books, 1st & 20th anniv. edition (1979 & 1999), p. 73.
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = n + sqrt(2n) + o(n^(1/2)). - M. F. Hasler, Jun 04 2008 [proved in Jubin's paper].
|
|
|
MATHEMATICA
|
(* h stands for Hofstadter's sequence A005228 *) h[1] = 1; h[2] = 3; h[n_] := h[n] = 2*h[n-1] - h[n-2] + If[ MemberQ[ Array[h, n-1], h[n-1] - h[n-2] + 1], 2, 1]; Differences[ Array[h, 69]] (* Jean-François Alcover, Oct 06 2011 *)
|
|
|
PROG
|
(PARI) {a=b=t=1; for(i=1, 100, while(bittest(t, b++), ); print1(b", "); t+=1<<b+1<<a+=b)} \\ M. F. Hasler, Jun 04 2008
(Haskell)
import Data.List (delete)
a030124 n = a030124_list !! n
a030124_list = figureDiff 1 [2..] where
figureDiff n (x:xs) = x : figureDiff n' (delete n' xs) where n' = n + x
|
|
|
CROSSREFS
|
Cf. A005228, A030124, A037257, A037258, A037259, A061577, A140778, A129198, A129199, A100707, A093903, A005132, A006509, A081145, A099004, A225376, A225377, A225378, A225385, A225386, A225387, A225687.
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
| |
|
|
|
1, 2, 3, 4, 5, 6, 9, 7, 8, 14, 10, 11, 18, 12, 13, 24, 15, 16, 30, 17, 19, 34, 20, 21, 39, 22, 23, 43, 25, 26, 50, 27, 28, 54, 29, 31, 57, 33, 32, 35, 36, 70, 37, 38, 73, 40, 41, 78, 42, 44, 85, 45, 46, 90, 47, 48, 94, 49, 51, 97, 52, 53, 104, 55, 56, 109, 58, 59, 116, 61, 60, 62, 63
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
The (signed) differences themselves are in A099004, but this sequence is important enough to have its own entry.
Conjectured (see the Slater-Velez and Velez articles) to be a permutation of the positive integers.
It appears that the terms line on two lines (this is true for the first million terms): see A308016-A308020.
|
|
|
LINKS
|
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A308021
|
|
Start at n=1. Fill in a(n) with a value d > 0 not used earlier such that n-d or n+d is the smallest possible index not visited earlier, then continue with that index.
|
|
+10
5
|
|
|
|
1, 2, 5, 3, 7, 10, 4, 6, 12, 15, 17, 8, 20, 9, 22, 11, 25, 27, 29, 14, 13, 33, 35, 37, 16, 40, 18, 19, 42, 45, 47, 49, 21, 24, 52, 55, 23, 58, 61, 62, 30, 26, 65, 66, 28, 68, 34, 31, 71, 74, 76, 79, 81, 39, 32, 83, 86, 36, 89, 43, 38, 91, 93, 96, 99, 41, 101, 50, 103, 106, 44, 108, 54, 111, 46, 113, 117, 48, 57, 118, 51, 120, 123
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
A variant of Recamán's sequence: start at n=1, a(1)=1, then iterate: let n' = n - a(n) if this n' > 0 and was not visited earlier, otherwise n' = n + a(n). Then let n'' <> n' be the smallest index not visited earlier (a(n'') not yet defined) such that the value |n'-n''| was not yet used (meaning not yet a value of any a(i)). Set a(n') = |n'-n''| and continue with n = n'. [Name and Comment suggested by M. F. Hasler at the request of the authors.]
Conjectured to be a permutation of the positive integers. The conjectured inverse permutation is given in A308049. - M. F. Hasler, May 10 2019
The sequence is given by the following formula. Let R(t) = A081145(t). Then for all t >= 1, a(R(t)) = |R(t+1)-R(t)|.
For example, for t=10, R(10)=20, R(11)=6, and a(R(10)) = a(20) = |6-20| = 14.
Since it is known that {R(t): t>=1} is a permutation of the positive integers (it is the "Slater-Velez permutation of the first kind"), this specifies a(n) for all n.
The connection with the definition as interpreted above by M. F. Hasler is that at step t of the procedure, n' is R(t) = A081145(t), n'' is R(t+1) = A081145(t+1), and we calculate a(R(t)) = |n'-n''| = |R(t)-R(t+1)|.
The conjecture that {a(n)} is a permutation of the positive integers is equivalent to Slater and Velez's conjecture (see references) that the absolute values of the first differences of A081145 are also a permutation of the positive integers. This problem appears to be still unsolved. (End)
|
|
|
REFERENCES
|
P. J. Slater and W. Y. Velez, Permutations of the Positive Integers with Restrictions on the Sequence of Differences, II, Pacific Journal of Mathematics, Vol. 82, No. 2, 1979, 527-531.
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
a(1) = 1 drives us to the empty cell a(2) since we can't go further to the left. We fill this cell with the number 2 which is the smallest integer not used before and thus allows us to go to the leftmost possible empty cell, 2 + 2 = 4. (There are no empty places to the left and we can't go to 3 = 2 + 1 since a step 1 has already been used.) So we have a(2) = 2.
a(2) = 2 drives us to the empty cell a(4). We see that the leftmost empty cell a(3) cannot be reached from a(4) since a step of 1 has already been used. We thus fill the cell a(4) with the smallest integer not used before, a(4) = 3.
a(4) = 3 drives us to the empty cell a(7). We see that the leftmost empty cell a(3) can now be reached from a(7) if we fill a(7) with 4; we have thus a(7) = 4.
a(7) = 4 drives us to the empty cell a(3), which is the one we wanted to fill. We fill a(3) with 5 which is the smallest integer not leading to a contradiction, whence a(3) = 5.
a(3) = 5 drives us to the empty cell a(8). We would like to fill this cell with 3, as this 3 would allow us to fill the leftmost empty cell of the sequence - but 3 has been used before; thus we'll have a(8) = 6.
a(8) = 6 drives us to the empty cell a(14). We fill a(14) with 9 as this will allow us to reach the leftmost empty cell of the sequence, whence a(14) = 9.
a(14) = 9 drives us to the empty cell a(5). We fill a(5) with 7 as this is the smallest integer not leading to a contradiction, so we have a(5) = 7, etc.
|
|
|
PROG
|
(PARI) {A=vector(N=199); n=1; while (n<=N, S=Set(A); Z=select(t->!t, A, 1); for (i=1, #Z, Z[i]!=n||next; setsearch(S, abs(n-z=Z[i]))&& next; A[n]=abs(n-z); n=z; next(2)); break); if(#Z, A[1..Z[1]-!A[Z[1]]], A)} \\ M. F. Hasler, May 09 2019
|
|
|
CROSSREFS
|
Cf. A308049 (conjectured inverse permutation).
|
|
|
KEYWORD
|
base,nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
| |
|
|
|
3, 1, 7, 2, 14, 13, 12, 5, 11, 10, 6, 4, 31, 26, 27, 9, 22, 28, 8, 15, 53, 51, 50, 55, 52, 54, 48, 61, 58, 56, 62, 57, 59, 23, 39, 49, 20, 47, 44, 46, 43, 42, 45, 25, 29, 30, 17, 16, 18, 21, 19, 124, 107, 106, 109, 110, 111, 24, 118, 117, 114, 125, 127, 104
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
COMMENTS
|
All terms are distinct.
|
|
|
LINKS
|
|
|
|
PROG
|
(Perl) See Link section.
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A258137
|
|
Absolute first differences of the lexicographically earliest sequence of odd positive integers such that the terms and their absolute first differences are all distinct.
|
|
+10
2
|
|
|
|
2, 4, 6, 8, 10, 12, 18, 14, 16, 28, 20, 22, 36, 24, 26, 48, 30, 32, 60, 34, 38, 68, 40, 42, 78, 44, 46, 86, 50, 52, 100, 54, 56, 108, 58, 62, 114, 66, 64, 70, 72, 140, 74, 76, 146, 80, 82, 156, 84, 88, 170, 90, 92, 180, 94, 96, 188, 98, 102, 194, 104, 106, 208
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
COMMENTS
|
All terms are even.
|
|
|
LINKS
|
|
|
|
FORMULA
|
|
|
|
MAPLE
|
b:= proc() false end:
g:= proc(n) option remember; local k;
if n=1 then b(1):= true; 1
else g(n-1); for k while b(k) or
b(abs(g(n-1)-k)) by 2 do od;
b(k), b(abs(g(n-1)-k)):= true$2; k
fi
end:
a:= n-> abs(g(n+1)-g(n)):
seq(a(n), n=1..101);
|
|
|
MATHEMATICA
|
b[_] = False;
g[n_] := g[n] = Module[{k},
If[n == 1, b[1] = True; 1,
g[n-1]; For[k = 1, b[k] ||
b[Abs[g[n-1] - k]], k += 2];
{b[k], b[Abs[g[n-1] - k]]} = {True, True}; k]];
a[n_] := Abs[g[n+1] - g[n]];
|
|
|
CROSSREFS
|
Absolute first differences of A258136.
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A371295
|
|
Value k at the n-th step of A371282, where multiplied values are positive and subtracted values are negative.
|
|
+10
2
|
|
|
|
2, 3, -1, 4, -17, 5, -11, 6, -16, 7, -49, 9, -54, 8, -62, 10, -89, 12, -120, 13, -143, 14, -168, 15, -194, 18, -271, 19, -305, 20, -341, 21, -378, 22, -440, 23, -483, 24, -527, 25, -599, 26, -649, 27, -701, 28, -755, 29, -811, 30, -869, 31, -929, 32, -991, 33
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
|
|
|
PROG
|
(Python)
from itertools import islice
def agen(): # generator of terms
mina, an, aset, mink, kset = 1, 1, {1}, 1, set()
while True:
k1, ak1, k2 = 0, mina, mink
if mina < an:
for ak1 in range(mina, an-mink+1):
if ak1 not in aset and an - ak1 not in kset:
k1 = an - ak1
break
while k2 in kset or an*k2 in aset:
k2 += 1
an, k = (an-k1, k1) if k1 > 0 else (an*k2, k2)
yield -k if k1 > 0 else k
aset.add(an)
kset.add(k)
while mina in aset: mina += 1
while mink in kset: mink += 1
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
sign
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
Search completed in 0.018 seconds
|
