A039966 -id:A039966 - cp's OEIS frontend

A309890 Lexicographically earliest sequence of positive integers without triples in weakly increasing arithmetic progression.

1, 1, 2, 1, 1, 2, 2, 4, 4, 1, 1, 2, 1, 1, 2, 2, 4, 4, 2, 4, 4, 5, 5, 8, 5, 5, 9, 1, 1, 2, 1, 1, 2, 2, 4, 4, 1, 1, 2, 1, 1, 2, 2, 4, 4, 2, 4, 4, 5, 5, 8, 5, 5, 9, 2, 4, 4, 5, 5, 10, 5, 5, 10, 10, 11, 13, 10, 11, 10, 11, 13, 10, 10, 12, 13, 10, 13, 11, 12, 20, 11, 1, 1, 2, 1, 1, 2, 2, 4, 4, 1, 1, 2, 1, 1, 2, 2, 4, 4, 2

Offset: 1

Sébastien Palcoux, Aug 21 2019

Formal definition: lexicographically earliest sequence of positive integers a(n) such that for any i > 0, there is no n > 0 such that 2a(n+i) = a(n) + a(n+2i) AND a(n) <= a(n+i) <= a(n+2i).
Sequence suggested by Richard Stanley as a variant of A229037. They differ from the 55th term. The numbers n for which a(n) = 1 are given by A003278, or equally by A005836 (Richard Stanley).
The sequence defined by c(n) = 1 if a(n) = 1 and otherwise c(n) = 0 is A039966 (although with a different offset). - N. J. A. Sloane, Dec 01 2019
Pleasant to listen to (button above) with Instrument no. 13: Marimba (and for better listening, save and convert to MP3).

Sébastien Palcoux, Table of n, a(n) for n = 1..100000
Sébastien Palcoux, On the first sequence without triple in arithmetic progression (version: 2019-08-21), second part, MathOverflow
Sébastien Palcoux, Table of n, a(n) for n = 1..1000000
Sébastien Palcoux, Density plot of the first 1000000 terms

Cf. A003278, A005836, A039966, A229037.

from itertools import count, islice
def A309890_gen(): # generator of terms
    blist = []
    for n in count(0):
        i, j, b = 1, 1, set()
        while n-(i<<1) >= 0:
            x, y = blist[n-2*i], blist[n-i]
            z = (y<<1)-x
            if x<=y<=z:
                b.add(z)
                while j in b:
                    j += 1
            i += 1
        blist.append(j)
        yield j
A309890_list = list(islice(A309890_gen(),30)) # Chai Wah Wu, Sep 12 2023

# %attach SAGE/ThreeFree.spyx
from sage.all import *
cpdef ThreeFree(int n):
     cdef int i,j,k,s,Li,Lj
     cdef list L,Lb
     cdef set b
     L=[1,1]
     for k in range(2,n):
          b=set()
          for i in range(k):
               if 2*((i+k)/2)==i+k:
                    j=(i+k)/2
                    Li,Lj=L[i],L[j]
                    s=2*Lj-Li
                    if s>0 and Li<=Lj:
                         b.add(s)
          if 1 not in b:
               L.append(1)
          else:
               Lb=list(b)
               Lb.sort()
               for t in Lb:
                    if t+1 not in b:
                         L.append(t+1)
                         break
     return L

A120880 G.f. satisfies: A(x) = A(x^3)(1 + 2x + x^2); thus a(n) = 2^A062756(n), where A062756(n) is the number of 1's in the ternary expansion of n.

Original entry on oeis.org

1, 2, 1, 2, 4, 2, 1, 2, 1, 2, 4, 2, 4, 8, 4, 2, 4, 2, 1, 2, 1, 2, 4, 2, 1, 2, 1, 2, 4, 2, 4, 8, 4, 2, 4, 2, 4, 8, 4, 8, 16, 8, 4, 8, 4, 2, 4, 2, 4, 8, 4, 2, 4, 2, 1, 2, 1, 2, 4, 2, 1, 2, 1, 2, 4, 2, 4, 8, 4, 2, 4, 2, 1, 2, 1, 2, 4, 2, 1, 2, 1, 2, 4, 2, 4, 8, 4, 2, 4, 2, 4, 8, 4, 8, 16, 8, 4, 8, 4, 2, 4, 2, 4, 8, 4

Offset: 0

Paul D. Hanna, Jul 11 2006

More generally, if g.f. of {a(n)} satisfies: A(x) = A(x^3)*(1 + b*x + c*x^2), then a(n) = b^A062756(n)*c^A081603(n), where A062756(n) is the number of 1's and A081603(n) is the number of 2's, in the ternary expansion of n. This sequence is not the same as A059151.
a(n) is the number of entries in the n-th row of Pascal's triangle that are congruent to 1 mod 3 minus the number of entries that are congruent to 2 mod 3. - N. Sato, Jun 22 2007 (see Liu (1991))
This sequence pertains to genotype Punnett square mathematics. Start with X = 1. Each hybrid cross involves the equation X:2X:X. Therefore, the ratio in the first (mono) hybrid cross is X=1:2X=2(1) or 2:X=1; or 1:2:1. When you move up to the next hybridization level, replace the previous cross ratio with X. X now represents 3 numbers—1:2:1. Therefore, the ratio in the second (di) hybrid cross is X = (1:2:1):2X = [2(1):2(2):2(1)] or (2:4:2):X = (1:2:1). Put it together and you get 1:2:1:2:4:2:1:2:1. Each time you move up a hybridization level, replace the previous ratio with X, and use the same equation—X:2X:X to get its ratio. - John Michael Feuk, Dec 10 2011
Also number of ways to write n as sum of two nonnegative numbers having in ternary representation no 3; see also A205565. - Reinhard Zumkeller, Jan 28 2012

			Records are 2^n at positions: 0,1,4,13,40,121,...,(3^n-1)/2,... (n>=0).
A(x) = 1 + 2*x + x^2 + 2*x^3 + 4*x^4 + 2*x^5 + x^6 + 2*x^7 + x^8 +...

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Andy Liu, Solution to Problem 2, Crux Mathematicorum, 17 (1991), 5-6.

Cf. A117947, A039966, A062756, A081603.

a120880 n = sum $ map (a039966 . (n -)) $ takeWhile (<= n) a005836_list
-- Reinhard Zumkeller, Jan 28 2012

Nest[ Join[#, 2 #, #] &, {1}, 5] (* Robert G. Wilson v, Jul 27 2014 *)

PARI
```
a(n)=if(n==0,1,a(n\3)*2^((n%3)%2))
```

a((3^n+1)/2) = 2^n; a(n) = a(floor(n/3))*2^[[n (mod 3)] (mod 2)], with a(0)=1.
G.f.: A(x) = prod_{n>=0} (1 + x^(3^n))^2.
Self-convolution of A039966.
Row sums of triangle A117947(n,k) = balanced ternary of C(n,k) mod 3.

A081611 Number of numbers <= n having no 2 in their ternary representation.

Original entry on oeis.org

1, 2, 2, 3, 4, 4, 4, 4, 4, 5, 6, 6, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 10, 10, 11, 12, 12, 12, 12, 12, 13, 14, 14, 15, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16

Offset: 0

Reinhard Zumkeller, Mar 23 2003

nonn

a(n) is also the size of the subset of [1..n] when numbers are added greedily so as to not contain a 3-term arithmetic progression, i.e., according to A003278: a(n) = the largest k such that A003278(k) <= n. (Cf. A003002, the size of the optimal (largest) 3-free subset of [1..n].) - Shreevatsa R, Oct 19 2009

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000

Cf. A003278, A007089, A039966, A081603, A081608, A061392, A081610.

a081611 n = a081611_list !! n
a081611_list = scanl1 (+) a039966_list
-- Reinhard Zumkeller, Jan 28 2012

R:=PowerSeriesRing(Integers(), 100); Coefficients(R!( (&*[1+x^(3^k): k in [0..5]])/(1-x) )); // G. C. Greubel, Mar 29 2019

CoefficientList[Series[Product[1+x^(3^k), {k,0,5}]/(1-x), {x,0,100}], x] (* G. C. Greubel, Mar 29 2019 *)

{a(n)=local(A,m); if(n<0, 0, m=1; A=1+O(x); while(m<=n, m*=3; A=(1+x)*(1+x+x^2)*subst(A,x,x^3)); polcoeff(A,n))} /* Michael Somos, Aug 31 2006 */

first(n)=my(s,t); vector(n,k,t=Set(digits(k,3)); s+=t[#t]<2) \\ Charles R Greathouse IV, Sep 02 2015

my(x='x+O('x^100)); Vec(prod(k=0,5,1+x^(3^k))/(1-x)) \\ G. C. Greubel, Mar 29 2019

from gmpy2 import digits
def A081611(n):
    l = (s:=digits(n,3)).find('2')
    if l >= 0: s = s[:l]+'1'*(len(s)-l)
    return int(s,2)+1 # Chai Wah Wu, Dec 05 2024

(product(1+x^(3^k) for k in (0..5))/(1-x)).series(x, 100).coefficients(x, sparse=False) # G. C. Greubel, Mar 29 2019

a(n) + A081610(n) = n+1.
From Michael Somos, Aug 31 2006: (Start)
G.f. A(x) satisfies A(x)=(1+x)*(1+x+x^2)*A(x^3).
G.f.: (1/(1-x))*Product_{k>=0} (1+x^(3^k)).
a(n) = a(n-1) + A039966(n). (End)

A112345 Number of partitions of n into distinct perfect powers.

Original entry on oeis.org

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

Offset: 0

Reinhard Zumkeller, Sep 05 2005

nonn

			a(40) = #{36+4, 32+8, 27+9+4} = 3.

Vaclav Kotesovec, Table of n, a(n) for n = 0..10000
Eric Weisstein's World of Mathematics, Perfect Power
Eric Weisstein's World of Mathematics, Partition

Cf. A001597, A000009, A033461, A039966, A112344, A284171.

G.f.: Product_{k>=2} (1 + x^A001597(k)). - Ilya Gutkovskiy, Mar 21 2017

a(0)=1 prepended by Ilya Gutkovskiy, Mar 21 2017

A117944 Triangle related to powers of 3 partitions of n.

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1

Offset: 0

Paul Barry, Apr 05 2006

Inverse is A117945.

Row sums of inverse are A039966.

			Triangle begins
  1;
  0, 1;
  1, 0, 1;
  0, 0, 0, 1;
  0, 0, 0, 0, 1;
  0, 0, 0, 1, 0, 1;
  1, 0, 0, 0, 0, 0, 1;
  0, 1, 0, 0, 0, 0, 0, 1;
  1, 0, 1, 0, 0, 0, 1, 0, 1;
  0, 0, 0, 0, 0, 0, 0, 0, 0, 1;
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1;
  0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1;

G. C. Greubel, Rows n = 0..50 of the triangle, flattened

Cf. A039966, A117939, A117943, A117945.

T[n_, k_]:= Mod[Sum[JacobiSymbol[Binomial[n, j], 3]*JacobiSymbol[Binomial[n-j, k], 3], {j,0,n}], 2];
Table[T[n, k], {n,0,15}, {k,0,n}]//Flatten (* G. C. Greubel, Oct 29 2021 *)

def A117944(n, k): return ( sum(jacobi_symbol(binomial(n, j), 3)*jacobi_symbol(binomial(n-j, k), 3) for j in (0..n)) )%2
flatten([[A117944(n, k) for k in (0..n)] for n in (0..15)]) # G. C. Greubel, Oct 29 2021

Triangle T(n,k) = Sum_{j=0..n} L(C(n,j)/3)*L(C(n-j,k)/3) mod 2, where L(j/p) is the Legendre symbol of j and p.
T(n, k) = A117939(n,k) mod 2.
T(n, k) = A117939^(-1)(n,k) mod 2.
Sum_{k=0..n} T(n, k) = A117943(n).

A060374 a(n)=p+q, where n=p-q and p, q, p+q are in A005836 (integers written without 2 in base 3).

Original entry on oeis.org

0, 1, 4, 3, 4, 13, 12, 13, 10, 9, 10, 13, 12, 13, 40, 39, 40, 37, 36, 37, 40, 39, 40, 31, 30, 31, 28, 27, 28, 31, 30, 31, 40, 39, 40, 37, 36, 37, 40, 39, 40, 121, 120, 121, 118, 117, 118, 121, 120, 121, 112, 111, 112, 109, 108, 109, 112, 111, 112, 121, 120, 121, 118

Offset: 0

Claude Lenormand (claude.lenormand(AT)free.fr), Apr 02 2001

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Zoran Sunic, Tree morphisms, transducers and integer sequences, arXiv:math/0612080 [math.CO], 2006.

Cf. A005836, A039966, A060372, A060373.

a060374 n = f $ dropWhile (< n) a005836_list where
   f (p:ps) | a039966 (p-n) == 1 && a039966 (2*p-n) == 1 = 2*p - n
            | otherwise                                  = f ps
-- Reinhard Zumkeller, Sep 29 2011

Definition clarified by Zoran Sunic, Feb 16 2006

A104406 Number of numbers <= n having no 2 in ternary representation.

Original entry on oeis.org

1, 1, 2, 3, 3, 3, 3, 3, 4, 5, 5, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 9, 9, 10, 11, 11, 11, 11, 11, 12, 13, 13, 14, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15

Offset: 1

Reinhard Zumkeller, Mar 05 2005

nonn

Partial sums of A039966: a(n) = Sum(A039966(k): 1<=k<=n).

N. J. A. Sloane, Table of n, a(n) for n = 1..10000

Cf. A005836, A004642, A039966.

This is a lower bound for A003002.

A117945 Triangle related to powers of 3 partitions of n.

Original entry on oeis.org

1, 0, 1, -1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, -1, 0, 1, -1, 0, 0, 0, 0, 0, 1, 0, -1, 0, 0, 0, 0, 0, 1, 1, 0, -1, 0, 0, 0, -1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1

Offset: 0

Paul Barry, Apr 05 2006

Row sums are A039966.

Inverse of A117944.

			Triangle begins
   1;
   0,  1;
  -1,  0,  1;
   0,  0,  0,  1;
   0,  0,  0,  0, 1;
   0,  0,  0, -1, 0, 1;
  -1,  0,  0,  0, 0, 0,  1;
   0, -1,  0,  0, 0, 0,  0, 1;
   1,  0, -1,  0, 0, 0, -1, 0, 1;
   0,  0,  0,  0, 0, 0,  0, 0, 0,  1;
   0,  0,  0,  0, 0, 0,  0, 0, 0,  0, 1;
   0,  0,  0,  0, 0, 0,  0, 0, 0, -1, 0, 1;

G. C. Greubel, Rows n = 0..50 of the triangle, flattened

Cf. A039966, A117944.

M[n_, k_]:= M[n, k] = If[k>n, 0, Mod[Sum[JacobiSymbol[Binomial[n, j], 3]*JacobiSymbol[Binomial[n-j, k], 3], {j,0,n}], 2], 0];
m:= m= With[{q=60}, Table[M[n, k], {n,0,q}, {k,0,q}]];
T[n_, k_]:= Inverse[m][[n+1, k+1]];
Table[T[n, k], {n,0,15}, {k,0,n}]//Flatten (* G. C. Greubel, Oct 29 2021 *)

A205565 Number of ways of writing n = u + v with u <= v, and u,v having in ternary representation no 3.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 2, 4, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 2, 4, 2, 1, 2, 1, 2, 4, 2, 4, 8, 4, 2, 4, 2, 1, 2, 1, 2, 4, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 2, 4, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 2, 4

Offset: 0

Reinhard Zumkeller, Jan 28 2012

nonn

			a(30) = #{0+30, 3+27} = 2;
a(31) = #{0+31, 1+30, 3+28, 4+27} = 4;
a(32) = #{1+31, 4+28} = 2;
a(33) = #{3+30} = 1;
a(34) = #{3+31, 4+30} = 2;
a(35) = #{4+31} = 1;
a(36) = #{0+36, 9+27} = 2;
a(37) = #{0+37, 1+36, 9+28, 10+27} = 4;
a(38) = #{1+37, 10+28} = 2;
a(39) = #{0+39, 3+36, 9+30, 12+27} = 4;
a(40) = #{0+40, 1+39, 3+37, 4+36, 9+31, 10+30, 12+28, 13+27} = 8.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000

Cf. A039966, A005836, A120880.

a205565 n = sum $ map (a039966 . (n -)) $
                  takeWhile (<= n `div` 2) a005836_list

A294106 Sum of products of terms in all partitions of 3*n into distinct powers of 3.

Original entry on oeis.org

1, 3, 0, 9, 27, 0, 0, 0, 0, 27, 81, 0, 243, 729, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 81, 243, 0, 729, 2187, 0, 0, 0, 0, 2187, 6561, 0, 19683, 59049, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

Offset: 0

Seiichi Manyama, Oct 28 2017

nonn

			n | partitions of 3*n into distinct powers of 3 | a(n)
------------------------------------------------------
1 | 3                                           |  3
2 |                                             |  0
3 | 9                                           |  9
4 | 9 + 3                                       | 27

Seiichi Manyama, Table of n, a(n) for n = 0..1000

Cf. A029930, A039966, A294298.

cp's OEIS Frontend

A309890 Lexicographically earliest sequence of positive integers without triples in weakly increasing arithmetic progression.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

SageMath

A120880 G.f. satisfies: A(x) = A(x^3)*(1 + 2*x + x^2); thus a(n) = 2^A062756(n), where A062756(n) is the number of 1's in the ternary expansion of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

A081611 Number of numbers <= n having no 2 in their ternary representation.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

PARI

PARI

PARI

Python

Sage

Formula

A112345 Number of partitions of n into distinct perfect powers.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions

A117944 Triangle related to powers of 3 partitions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Sage

Formula

A060374 a(n)=p+q, where n=p-q and p, q, p+q are in A005836 (integers written without 2 in base 3).

Views

Author

Keywords

Links

Crossrefs

Programs

Haskell

Extensions

A104406 Number of numbers <= n having no 2 in ternary representation.

Views

Author

Keywords

Comments

Links

Crossrefs

A117945 Triangle related to powers of 3 partitions of n.

Views

A120880 G.f. satisfies: A(x) = A(x^3)(1 + 2x + x^2); thus a(n) = 2^A062756(n), where A062756(n) is the number of 1's in the ternary expansion of n.