A322523 a(n) is the least nonnegative integer k for which there does not exist i < j with i+j=n and a(i)=a(j)=k.
0, 0, 1, 0, 1, 1, 0, 2, 2, 0, 2, 1, 0, 1, 2, 0, 3, 2, 0, 3, 1, 0, 1, 3, 0, 3, 3, 0, 3, 1, 0, 1, 3, 0, 2, 2, 0, 2, 1, 0, 1, 2, 0, 4, 3, 0, 4, 1, 0, 1, 4, 0, 4, 3, 0, 4, 1, 0, 1, 4, 0, 2, 2, 0, 2, 1, 0, 1, 2, 0, 4, 4, 0, 4, 1, 0, 1, 4, 0, 4, 4, 0, 4, 1, 0, 1, 4, 0, 2, 2, 0, 2, 1, 0, 1, 2, 0, 3, 4, 0
Offset: 1
Examples
a(1) = 0. a(2) = 0. a(3) = 1 (because a(1) and a(2) both equal 0). a(5) = 1 (because a(1) and a(4) both equal 0). a(8) = 2 (because a(1) and a(7) equal 0, and a(3) and a(5) equal 1).
Links
- Jianing Song, Table of n, a(n) for n = 1..10000 (first 995 terms from Aidan Clarke)
Programs
-
Maple
for n from 1 to 100 do forbid:= {seq(A[i],i= select(i -> A[i]=A[n-i],[$1..(n-1)/2]))}; if forbid = {} then A[n]:= 0 else A[n]:= min({$0..max(forbid)+1} minus forbid) fi; od: seq(A[i],i=1..100); # Robert Israel, Sep 06 2019 -
PARI
least(v, n) = {my(found = []); for (i=1, n, if (i >= n-i, break, if (v[i] == v[n-i], found = Set(concat(found, v[i]))));); if (#found == 0, return(0)); my(m = vecmax(found)); for (i=0, m, if (!vecsearch(found, i), return (i))); return (m+1);} lista(nn) = {my(v = vector(nn)); for (n=1, nn, v[n] = least(v, n);); v;} \\ Michel Marcus, Sep 07 2019 -
PARI
a(n) = my(v=valuation(n,3)); n=n/3^v; if(n==2 || n%3==1, v, A215879((n-5)/3)+1+v) \\ Jianing Song, Aug 23 2022; see A215879 for its program
-
Python
def A322523(n): c, m = 0, n while not (a:=divmod(m,3))[1]: c += 1 m = a[0] if m==2 or m%3==1: return c m = (m+1)//3-2 while (a:=divmod(m,3))[1]: c += 1 m = a[0] return c+1 # Chai Wah Wu, Oct 15 2022
Formula
a(n) = 0 iff n belongs to A033627. - Rémy Sigrist, Sep 06 2019
From Jianing Song, Aug 23 2022: (Start)
Properties of this sequence:
(1) a(n) = a(n/3) + 1 for n == 0 (mod 3).
Proof is based on induction on n. Obviously a(n) != 0. For 1 <= e <= a(n/3), there exists i+j = n/3, i < j such that a(i) = a(j) = e-1, by induction hypothesis we have a(3*i) = a(3*j) = e, so a(n) != e. a(n) = a(n/3) + 1 is OK. Suppose otherwise that n = i+j, i < j and a(i) = a(j) = a(n/3) + 1 > 0, then i,j == 0 (mod 3), by induction hypothesis we have a(i/3) = a(j/3) = a(n/3), a contradiction.
(2) a(n) = A215879((n-5)/3) + 1 for n == 2 (mod 3) and n > 2.
If A215879((n-5)/3) = t, then n = 3*(Sum_{0<=r<=t-1} d_r*3^r + O(3^(t+1))) + 5, d_r = 1 or 2. Suppose that a(m) = A215879((m-5)/3) + 1 for m == 2 (mod 3) and 2 < n < m.
Obviously a(n) != 0. From (1) we know that a(3^e) = a(2*3^e) = t. For 1 <= e <= t, n - d_e*3^e = 3*(Sum_{0<=r<=t-1, r!=e-1} d_r*3^r + O(3^(t+1))) + 5 = 3*(Sum_{0<=r<=e-2} d_r*3^r + O(3^e)) + 5, so A215879((n-d_e*3^e-5)/3) = e-1. Since 5 <= n - d_e*3^e == 2 (mod 3), by induction hypothesis we have a(n-d_e*3^e) = e = a(d_e*3^e), so a(n) != e.
a(n) = t+1 is OK. Suppose otherwise that n = i+j, i != j and a(i) = a(j) = t+1 > 0, then {i,j} == {0,2} (mod 3) and i,j > 2. Suppose that i == 2 (mod 3), by induction hypothesis A215879((i-5)/3) = t. Write i = 3*(Sum_{0<=r<=t-1} d'_r*3^r + O(3^(t+1))) + 5, 1 <= d'_r <= d_r. If d'_r = d_r for all r, then j = n-i is divisible by 3^(t+2), so a(j) >= t+2, a contradiction. If d'_r != d_r for some r, then j = 3^(r_0+1) + O(3^(r_0+2)) where r_0 is the smallest index such that d'_r != d_r, so a(j) = r_0+1 + a(1+O(3^1)) = r_0+1 <= t, also a contradiction.
Recursive formulas:
a(n) = 0 for n = 2 or n == 1 (mod 3);
a(n) = 1 for n == 5 (mod 9);
a(n) = a(n/3) + 1 for n == 0 (mod 3);
a(n) = a((n+4)/3) + 1 for n == 2 (mod 9) and n > 2;
a(n) = a((n+7)/3) + 1 for n == 8 (mod 9).
Let A_1 = {3}, B_1 = {5}, A_{t+1} = {3*n: n in A_t, B_t}, B_{t+1} = {3*n-7, 3*n-4: n in B_t}, then for t >= 1, {n: a(n) = t} = (Union_{k>=0} {n+k*3^(t+1): n in A_t, B_t}) U {2*3^t}.
General formula: write n = s*3^t, gcd(s,3) = 1, then a(n) = t if s = 2 or s == 1 (mod 3), A215879((s-5)/3) + 1 + t otherwise. (End)
Comments