|
| |
|
|
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.
|
|
4
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,8
|
|
|
COMMENTS
|
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.
The variant where we drop the condition "i < j" corresponds to A007814. - Rémy Sigrist, Sep 06 2019
|
|
|
LINKS
|
|
|
|
FORMULA
|
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)
|
|
|
EXAMPLE
|
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).
|
|
|
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:
|
|
|
PROG
|
(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)
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]
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
