|
%I #76 Oct 15 2022 08:50:51
%S 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,
%T 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,
%U 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
%N 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.
%C If x is an integer that we are checking whether it is an option for a(n), at position n = 3(3^(x+1)-1)/2 there appears to begin a repeating sequence (containing 3^(x+1) terms) of whether it can or cannot be used for a(n) that continues infinitely.
%C The variant where we drop the condition "i < j" corresponds to A007814. - _Rémy Sigrist_, Sep 06 2019
%H Jianing Song, <a href="/A322523/b322523.txt">Table of n, a(n) for n = 1..10000</a> (first 995 terms from Aidan Clarke)
%F a(n) = 0 iff n belongs to A033627. - _Rémy Sigrist_, Sep 06 2019
%F From _Jianing Song_, Aug 23 2022: (Start)
%F Properties of this sequence:
%F (1) a(n) = a(n/3) + 1 for n == 0 (mod 3).
%F 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.
%F (2) a(n) = A215879((n-5)/3) + 1 for n == 2 (mod 3) and n > 2.
%F 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.
%F 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.
%F 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.
%F Recursive formulas:
%F a(n) = 0 for n = 2 or n == 1 (mod 3);
%F a(n) = 1 for n == 5 (mod 9);
%F a(n) = a(n/3) + 1 for n == 0 (mod 3);
%F a(n) = a((n+4)/3) + 1 for n == 2 (mod 9) and n > 2;
%F a(n) = a((n+7)/3) + 1 for n == 8 (mod 9).
%F 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}.
%F 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)
%e a(1) = 0.
%e a(2) = 0.
%e a(3) = 1 (because a(1) and a(2) both equal 0).
%e a(5) = 1 (because a(1) and a(4) both equal 0).
%e a(8) = 2 (because a(1) and a(7) equal 0, and a(3) and a(5) equal 1).
%p for n from 1 to 100 do
%p forbid:= {seq(A[i],i= select(i -> A[i]=A[n-i],[$1..(n-1)/2]))};
%p if forbid = {} then A[n]:= 0 else A[n]:= min({$0..max(forbid)+1} minus forbid) fi;
%p od:
%p seq(A[i],i=1..100); # _Robert Israel_, Sep 06 2019
%o (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);}
%o lista(nn) = {my(v = vector(nn)); for (n=1, nn, v[n] = least(v, n);); v;} \\ _Michel Marcus_, Sep 07 2019
%o (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
%o (Python)
%o def A322523(n):
%o c, m = 0, n
%o while not (a:=divmod(m,3))[1]:
%o c += 1
%o m = a[0]
%o if m==2 or m%3==1: return c
%o m = (m+1)//3-2
%o while (a:=divmod(m,3))[1]:
%o c += 1
%o m = a[0]
%o return c+1 # _Chai Wah Wu_, Oct 15 2022
%Y Cf. A007814, A033627, A218579.
%K nonn,easy
%O 1,8
%A _Aidan Clarke_, Aug 28 2019
|
