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$
    – ho boon suan
    Commented Feb 9 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$
    – Seva
    Commented Feb 9 at 11:37
  • $\begingroup$ @hoboonsuan amazing, thanks! I entered the first few numbers in the OEIS search engine and came up with nothing $\endgroup$
    – Dominic van der Zypen
    Commented Feb 9 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$
    – ho boon suan
    Commented Feb 9 at 13:26
  • $\begingroup$ Remarkable @Seva thanks for your effort! $\endgroup$
    – Dominic van der Zypen
    Commented Feb 10 at 5:15

1 Answer 1

Reset to default
5
$\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$
    – Sam Hopkins
    Commented Feb 10 at 18:35
  • 1
    $\begingroup$ @SamHopkins WOW! A bad habit to start working on a problem without studying what have other people done... $\endgroup$
    – Seva
    Commented Feb 10 at 18:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .