A235726 Lexicographically earliest sequence of positive integers such that a(nm) != a(n + m) for all positive integers n and m such that nm != n + m.

1, 2, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 3, 1, 2, 1, 2, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 2, 1, 2, 1, 3, 1, 2, 1, 3, 1, 2, 1, 3, 1, 2, 1, 2, 1, 2, 1, 5, 1, 2, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 2, 1, 4, 1, 2, 1, 4, 1, 2, 1

Offset: 1

Author

Peter Kagey, Apr 18 2017

Keywords

• nonn

Comments

a(n) != a(n-1) because a(n*1) = a((n-1)+1).

Records appear at: a(1) = 1, a(2) = 2, a(8) = 3, a(16) = 4, a(64) = 5, a(1024) = 6, a(4080) = 7, a(320000) = 8.

From Robert Israel, Apr 19 2017: (Start)

a(n) = 1 iff n is odd.

If n == 2 (mod 4), then a(n) = 2.

(End)

Examples

			For n = 8,
a(8) != 1 because a(1 + 7) != a(1 * 7);
a(8) != 2 because a(2 * 4) != a(2 + 4);
a(8) = 3.
		

Links

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

Crossrefs

Cf. A072670.

Programs

Haskell

a 1 = 1
a 4 = 2
a n = head $ filter (`notElem` disallowedValues) [1..] where
  disallowedValues = map a $ (n-1) : filter ( n `mod` d == 0) [1..n]
      divisorSum d = d + n `div` d

Maple

N:= 100: # to get a(1) to a(N)
A[1]:= 1: A[2]:= 2: A[3]:= 1: A[4]:= 2:
for n from 5 to N do
   if n::odd then A[n]:= 1
   else
     A[n]:= min({$2..n} minus {seq(A[q+n/q], q=numtheory:-divisors(n) minus {1,n})});
   fi
od:
seq(A[i],i=1..N); # Robert Israel, Apr 19 2017