login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A340488 a(n+1) = XOR(a(n),y) for n>=1, where y is the number of m < n such that a(m) = a(n); a(1)=0. 12
0, 0, 1, 1, 0, 2, 2, 3, 3, 2, 0, 3, 1, 3, 0, 4, 4, 5, 5, 4, 6, 6, 7, 7, 6, 4, 7, 5, 7, 4, 0, 5, 6, 5, 1, 2, 1, 5, 0, 6, 2, 6, 3, 7, 3, 6, 0, 7, 2, 7, 1, 4, 1, 7, 0, 8, 8, 9, 9, 8, 10, 10, 11, 11, 10, 8, 11, 9, 11, 8, 12, 12, 13, 13, 12, 14, 14 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,6

COMMENTS

It appears that the graph of the first n terms is similar to the graph of the first n/4 terms for sufficiently large values (n > 100).

It appears that among the first 4^n terms, each integer value less than 2^n appears at least (3/4)*2^n times. This would imply that every positive integer appears an infinite number of times.

Yet another variant of the Van Eck sequence A181391. - N. J. A. Sloane, Jan 10 2021

It follows from the definition that when m appears for the first time, it is immediately followed by m, and then if m is even by m+1. A340494 gives a conjectured generating function for when a number appears for the first time. - Rémy Sigrist and N. J. A. Sloane, Jan 10 2021

Conjectures from Rémy Sigrist, Jan 10 2021 (Start)

It appears that the positions of the 0's are given by A336190, and the "y" sequence appears to be A336033.

For a fixed k > 0, let b(n) be the position of the k-th occurrence of n in A340488, Then the sequence { b(n) - A340494(n) } has period 2^m for some m,

- for k = 2 we have period ( 1 ) (the second occurrence appear next to the first).

- for k = 3 we have period ( 4, 10, 4, 4 ),

- for k = 4 we have period (10, 32, 30, 6, 10, 14, 12, 6). (End)

Theorem: Every number appears.

Proof. (i) If there were only finitely many different numbers in the sequence then one number k (say) would appear infinitely often. As the number of k's reaches the next power of 2, 2^m say, we get a term >= 2^m. So the sequence is unbounded. Contradiction. So there are infinitely many different terms.

(ii) To show that every number appears, consider a k-bit number n, n < 2^k. Let a(m) be the first term >= 2^k, where a(m) = a(m-1) XOR y, with a(m-1) < 2^k and y >= 2^k. Let a(m-1) = t. Since this is at least the 2^k-th copy of t, the sequence contains t XOR 0, t XOR 1, t XOR 2, ..., t XOR 2^k-1, and so contains every number from 0 to 2^k-1, and in particular contains n. QED

  - Rémy Sigrist and N. J. A. Sloane, Jan 11 2021

Conjecture: Let pi_i(n) denote the number of occurrences of i in the first n terms. Then pi_0(n) >= pi_i(n) for all i, and the first time pi_0(n) = m, pi_i(n) < m for i>0. - N. J. A. Sloane, Jan 13 2021

LINKS

Rémy Sigrist, Table of n, a(n) for n = 1..25000

Ian Hutchinson, Graph of first 3500 terms

Rémy Sigrist, PARI program for A340488

EXAMPLE

We start with a(1) = 0. 0 has not appeared before, so we set a(2) to bitxor(0,0), or 0. There has now been one previous appearance of 0, so we set a(3) to bitxor(0,1), or 1. There has been no previous appearance of 1, so we set a(4) to 1. There has now been one previous appearance of 1, so we set a(5) to bitxor(1,1), or 0.

MAPLE

b:= proc(n) option remember; `if`(n<1, 0, b(n-1)+x^a(n)) end:

a:= proc(n) option remember; `if`(n=1, 0, (t->

      Bits[Xor](t, coeff(b(n-2), x, t)))(a(n-1)))

    end:

seq(a(n), n=1..100);  # Alois P. Heinz, Apr 14 2021

PROG

(Python)

a340488 = [0]

repeat = [0] # Running tally for occurrences of each value

for n in range(3414):

    if(a340488[-1] >= len(repeat)):

        repeat.append(0)

    newValue = (a340488[-1] ^ repeat[a340488[-1]])

    repeat[a340488[-1]] += 1

    a340488.append(newValue)

(PARI) See Links section.

CROSSREFS

Cf. A181391 (Van Eck), A340496 (partial sums), A340499 (first differences), A340500 (running maximum).

See A340494, A340495 for when n first appears.

Cf. also A336033, A336190.

Sequence in context: A327236 A191860 A109973 * A339456 A220517 A340328

Adjacent sequences:  A340485 A340486 A340487 * A340489 A340490 A340491

KEYWORD

nonn,nice,look

AUTHOR

Ian Hutchinson, Jan 09 2021

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 12 08:13 EDT 2021. Contains 344943 sequences. (Running on oeis4.)