login
A377225
a(0) = 0, a(1) = 1, a(2) = -1, a(3) = 2, and for n > 3, a(n) is the least integer (in absolute value) not yet in the sequence sharing a factor with a(n-1); in case of a tie, preference is given to the positive value.
1
0, 1, -1, 2, -2, 4, -4, 6, 3, -3, -6, 8, -8, 10, 5, -5, -10, 12, 9, -9, -12, 14, 7, -7, -14, 16, -16, 18, 15, -15, -18, 20, -20, 22, 11, -11, -22, 24, 21, -21, -24, 26, 13, -13, -26, 28, -28, 30, 25, -25, -30, 27, -27, 33, -33, 36, 32, -32, 34, 17, -17, -34
OFFSET
0,4
COMMENTS
This sequence is a variant of the EKG sequence (A064413) allowing negative values; both sequences share similar features.
For any pair of prime numbers p and q such that p < q, a multiple of q is always preceded by a multiple of p.
For any odd prime number p, the first multiple of p is followed by p, -p and 2*p or -2*p, in that order.
All prime numbers appear in the sequence:
- by contradiction: if the sequence is p-smooth for some prime number p appearing in the sequence,
- there are infinitely many multiples of some prime number q <= p in the sequence,
- so all multiples of q will show up, including q*r some some prime number r > p, a contradiction.
Hence, the sequence contains infinitely many even numbers, and so all even numbers will show up.
For any nonzero integer v, as there are infinitely many even multiples of v in the sequence, and these are all chances for v to be chosen, so v will eventually appear: this sequence is a bijection from the nonnegative integers (N) to the integers (Z).
Partials sums are nonnegative (for any n > 0, among the first n terms, a negative term, say -v, will always be cancelled by the corresponding positive term v appearing prior, but some positive term might be present without the corresponding negative term).
FORMULA
Sum_{k = 0..n} a(k) >= 0 for any n >= 0.
EXAMPLE
The first terms are:
n a(n) gcd(a(n-1), a(n))
-- ---- -----------------
0 0 N/A
1 1 1
2 -1 1
3 2 1
4 -2 2
5 4 2
6 -4 4
7 6 2
8 3 3
9 -3 3
10 -6 3
11 8 2
12 -8 8
13 10 2
14 5 5
15 -5 5
16 -10 5
PROG
(PARI) \\ See Links section.
(Python)
from math import gcd
from itertools import count, islice, product
def agen(): # generator of terms
a, m = [0, 1, -1, 2], 2
yield from a
an, aset = a[-1], set(a)
for n in count(4):
an = next(s*k for k in count(m) for s in [1, -1] if s*k not in aset and gcd(k, an) > 1)
yield an
aset.add(an)
while m in aset and -m in aset: m += 1
print(list(islice(agen(), 62))) # Michael S. Branicky, Oct 21 2024
CROSSREFS
Cf. A064413.
Sequence in context: A324104 A278233 A354753 * A354755 A354858 A128923
KEYWORD
sign
AUTHOR
Rémy Sigrist, Oct 20 2024
STATUS
approved