A269427 a(1) = 1, a(n) counts m < n for which n == a(m) (mod m).

1, 1, 2, 1, 4, 1, 3, 2, 4, 3, 3, 1, 7, 4, 2, 1, 7, 3, 4, 3, 4, 2, 6, 5, 7, 3, 2, 1, 10, 1, 6, 5, 6, 3, 3, 2, 8, 5, 6, 2, 5, 4, 6, 3, 6, 7, 6, 1, 10, 3, 3, 3, 9, 3, 5, 3, 7, 5, 8, 3, 7, 4, 6, 3, 5, 4, 7, 6, 7, 3, 4, 3, 9, 8, 7, 3, 6, 1, 6, 5, 6

Offset: 1

Author

Alec Jones, Feb 25 2016

Keywords

• easy
• nonn

Comments

I conjecture that this sequence is unbounded. Consider the first k terms of this sequence, and let L be the floor of log(k). If we count the times that each number 1,2,...,2L appears among the first k terms of this sequence, it appears that these sums form a normal distribution centered at L, so that L appears approximately k/10 times among the first k terms of this sequence. (For instance, in the first k = 10000 terms of the sequence, L = log(10000) = 9 appears 1174 times, a maximal count among any value that appears at all.) Thus the sequence appears to be unbounded.

The sequence is unbounded. For any k, consider k pairwise coprime integers m_1, ..., m_k. By the Chinese Remainder Theorem, there are infinitely many n such that n == a(m_j) (mod m_j) for each j, and thus a(n) >= k. - Robert Israel, Mar 21 2016

Examples

			a(1) = 1;
a(2) = 1 because 2 == a(1) (mod 1);
a(3) = 2 because 3 == a(1) (mod 1) and 3 == a(2) (mod 2);
a(4) = 1 because 4 == a(1) (mod 1);
a(5) = 4 because 5 == a(1) (mod 1), 5 == a(2) (mod 2), 5 == a(3) (mod 3), and 5 == a(4) (mod 4).
		

Links

• Peter Kagey, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A269423.

Programs

Java

int[] terms = new int[10000];
terms[0] = 1;
for (int i = 1; i < 10000; i++) {
    int count = 0;
    for (int j = 0; j < i; j++) {
        if (((i+1) - terms[j]) % (j+1) == 0) {
            count++;
        }
    }
    terms[i] = count;
}

Maple

N:= 200: # to get a(1) to a(N)
A:= Vector(N,1):
for m from 2 to N-1 do
  S:= [seq(A[m]+m*i,i=1..floor((N-A[m])/m))];
  A[S]:= map(`+`,A[S],1);
od:
convert(A,list); # Robert Israel, Mar 21 2016

Mathematica

a[1] = 1; a[n_] := a[n] = Count[Range[n - 1], m_ /; Mod[a[m], m] == Mod[n, m]]; Table[a@ n, {n, 81}] (* Michael De Vlieger, Mar 21 2016 *)

PARI

lista(nn) = {va = vector(nn); print1(va[1] = 1, ", "); for (n=2, nn, va[n] = sum(m=1, n-1, (Mod(va[m], m) == Mod(n, m))); print1(va[n], ", "););} \\ Michel Marcus, Feb 26 2016