5
$\begingroup$

$\newcommand{\N}{\mathbb{N}}$Let $\N$ denote the set of non-negative integers. We inductively define a sequence $a:\N\to\N$ by:

  • $a(0) = 0, a(1) = 1$ and
  • $a(n) = \big(\sum_{k=0}^{n-1}a(k)\big)\text{ mod } n$, for $n\geq 2$.

This sequence starts with $0, 1, 1, 2, 0, 4, 2, 3,...$; more members can be calculated with this ${\mathtt{C}}$ file. So far this sequence doesn't seem to be listed in the online encyclopedia of integer sequences (OEIS).

Question. Is $a$ surjective? If yes, is $a^{-1}(\{m\})$ infinite for all $m\in\N$?

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ oeis.org/A094405 $\endgroup$ Commented Feb 9, 2024 at 10:11
  • 2
    $\begingroup$ Having computed the first $10^9$ terms, it seems that, say, $19$ and $39$ are missing from this sequence. $\endgroup$ Commented Feb 9, 2024 at 11:37
  • $\begingroup$ @hoboonsuan amazing, thanks! I entered the first few numbers in the OEIS search engine and came up with nothing $\endgroup$ Commented Feb 9, 2024 at 13:20
  • 2
    $\begingroup$ a common trick is to search for your sequence with the first or first few terms omitted — i learned this the hard way when i submitted a sequence i thought was new to the OEIS only to be told that it was already on the OEIS, just without my first term $\endgroup$ Commented Feb 9, 2024 at 13:26
  • $\begingroup$ Remarkable @Seva thanks for your effort! $\endgroup$ Commented Feb 10, 2024 at 5:15

1 Answer 1

Reset to default
6
$\begingroup$

The sequence is not surjective and indeed, all of its terms starting from $a_{397}$ are equal to $97$.

Let $S_n:=a_0+\dotsb+a_{n}$.

Claim. We have $a_n=97$ and $S_n=97n+194$ for all $n\ge397$.

Once stated, this is easy to prove by induction.

Proof: The case $n=397$ is verified by a computation. Applying the induction hypothesis, we get $$ a_{n+1}\equiv S_n \equiv 97n+194 \equiv 97\pmod{n+1}. $$ Since both $a_{n+1}$ and $97$ reside in $[0,n-1]$, we have in fact $a_{n+1}=97$. Consequently, $S_{n+1}=S_n+a_{n+1}=(97n+194)+97=97(n+1)+194$.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Interestingly this was mentioned in a comment in the above-linked OEIS entry oeis.org/A094405: "Theorem. For all values of n>=397, a(n)=97. Proof. Let s(n) denote Sum[a(i), i=1..n-1]. Calculation shows that s(397)=38606=397*97+97. Thus a(397)=397*97+97 mod 397=97. Then s(398)=s(397)+97=398*97+97, giving a(398)=97. A simple inductive argument shows that a(397+k)=97 for all integers k>=0. - John W. Layman, Jun 07 2004" $\endgroup$ Commented Feb 10, 2024 at 18:35
  • 1
    $\begingroup$ @SamHopkins WOW! A bad habit to start working on a problem without studying what have other people done... $\endgroup$ Commented Feb 10, 2024 at 18:58

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.