A249031 -id:A249031 - cp's OEIS frontend

A075326 Anti-Fibonacci numbers: start with a(0) = 0, and extend by the rule that the next term is the sum of the two smallest numbers that are not in the sequence nor were used to form an earlier sum.

0, 3, 9, 13, 18, 23, 29, 33, 39, 43, 49, 53, 58, 63, 69, 73, 78, 83, 89, 93, 98, 103, 109, 113, 119, 123, 129, 133, 138, 143, 149, 153, 159, 163, 169, 173, 178, 183, 189, 193, 199, 203, 209, 213, 218, 223, 229, 233, 238, 243, 249, 253, 258, 263, 269, 273, 279, 283

Offset: 0

Amarnath Murthy, Sep 16 2002

In more detail, the sequence is constructed as follows: Start with a(0) = 0. The missing numbers are 1 2 3 4 5 6 ... Add the first two, and we get 3, which is therefore a(1). Cross 1, 2, and 1+2=3 off the missing list. The first two missing numbers are now 4 and 5, so a(2) = 4+5 = 9. Cross off 4,5,9 from the missing list. Repeat.
In other words, this is the sum of consecutive pairs in the sequence 1, 2, 4, 5, 6, 7, 8, 10, 11, 12, 14, 15, ..., (A249031) the complement to the present one in the natural numbers. For example, a(1)=1+2=3, a(2)=4+5=9, a(3)=6+7=13, ... - Philippe Lallouet (philip.lallouet(AT)orange.fr), May 08 2008
The new definition is due to Philippe Lalloue (philip.lallouet(AT)orange.fr), May 08 2008, while the name "anti-Fibonacci numbers" is due to D. R. Hofstadter, Oct 23 2014.
Original definition: second members of pairs in A075325.
If instead we take the sum of the last used non-term and the most recent (i.e., 1+2, 2+4, 4+5, 5+7, etc.), we get A008585. - Jon Perry, Nov 01 2014
The sequences a = A075325, b = A047215, and c = A075326 are the solutions of the system of complementary equations defined recursively as follows:
  a(n) = least new,
  b(n) = least new,
  c(n) = a(n) + b(n),
where "least new k" means the least positive integer not yet placed. For anti-tribonacci numbers, see A265389; for anti-tetranacci, see A299405. - Clark Kimberling, May 01 2018
We see the Fibonacci numbers 3, 13, 89 and 233 occur in this sequence of anti-Fibonacci numbers. Are there infinitely many Fibonacci numbers occurring in (a(n))? The answer is yes: at least 13% of the Fibonacci numbers occur in (a(n)). This follows from Thomas Zaslavsky's formula, which implies that the sequence A017305 = (10n+3) is a subsequence of (a(n)). The Fibonacci sequence A000045 modulo 10 equals A003893, and has period 60. In this period, the number 3 occurs 8 times. - Michel Dekking, Feb 14 2019
From Augusto Santi, Aug 16 2025: (Start)
If we apply the anti-Fibonacci algorithm to the set of natural numbers minus the multiples of 3, we get 5, 10, 20, 25, 35, 40, 50, ...; that is, all the multiples of 5 present in the restricted set used. It is quite curious that in this particular case the algorithm can be applied recursively to its own output, generating, at the generic step s, the subset of multiples of 5^s (see Mathematics StackExchange link).
Conjectures:
After the first 0, the residues (mod 5) all fall in the classes 3 and 4. More generally, for k-nacci sequences the residue classes (mod k^2+1) all fall in k consecutive ones, the first being ceiling((k^2+1)/2​).
It is known that the sequence contains the arithmetic progression 10k+3, 20k+9 and 40k+18. These three progressions cover, experimentally, the 87.5% = 7/8 of the entire sequence. The remaining terms all belong to two forms: 40k+38 and 40k+39.
The anti-Fibonacci sequence contains all the squares of the numbers of the form 10k+3 and 10k+7, and all the cubes of the numbers of the form 10k+7, for k>=0. (End)

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Wieb Bosma, Rene Bruin, Robbert Fokkink, Jonathan Grube, Anniek Reuijl, and Thian Tromp, Using Walnut to solve problems from the OEIS, arXiv:2503.04122 [math.NT], 2025. See pp. 7, 14.
Robbert Fokkink and Gandhar Joshi, Anti-recurrence sequences, arXiv:2506.13337 [math.NT], 2025. See pp. 2, 18.
D. R. Hofstadter, Anti-Fibonacci numbers, Oct 23 2014.
Augusto Santi, A conjecture on Anti-k-nacci numbers, Mathematics StackExchange, 2025.
Thomas Zaslavsky, Anti-Fibonacci Numbers: A Formula, Sep 26 2016

Cf. A008585, A075325, A075327, A249031, A249032 (first differences), A000045.

Cf. also A079523, A131323, A249031, A249032, A249406.

import Data.List ((\\))
a075326 n = a075326_list !! n
a075326_list = 0 : f [1..] where
   f ws@(u:v:_) = y : f (ws \\ [u, v, y]) where y = u + v
-- Reinhard Zumkeller, Oct 26 2014

# Maple code for M+1 terms of sequence, from N. J. A. Sloane, Oct 26 2014
c:=0; a:=[c]; t:=0; M:=100;
for n from 1 to M do
s:=t+1; if s in a then s:=s+1; fi;
t:=s+1; if t in a then t:=t+1; fi;
c:=s+t;
a:=[op(a),c];
od:
[seq(a[n],n=1..nops(a))];

(* Three sequences a,b,c as in Comments *)
z = 200;
mex[list_, start_] := (NestWhile[# + 1 &, start, MemberQ[list, #] &]);
a = {}; b = {}; c = {};
Do[AppendTo[a,
   mex[Flatten[{a, b, c}], If[Length[a] == 0, 1, Last[a]]]];
  AppendTo[b, mex[Flatten[{a, b, c}], Last[a]]];
  AppendTo[c, Last[a] + Last[b]], {z}];
Take[a, 100] (* A075425 *)
Take[b, 100] (* A047215 *)
Take[c, 100] (* A075326 *)
Grid[{Join[{"n"}, Range[0, 20]], Join[{"a(n)"}, Take[a, 21]],
  Join[{"b(n)"}, Take[b, 21]], Join[{"c(n)"}, Take[c, 21]]},
Alignment -> ".",
Dividers -> {{2 -> Red, -1 -> Blue}, {2 -> Red, -1 -> Blue}}]
(* Peter J. C. Moses, Apr 26 2018 *)
********
(* Sequence "a" via A035263 substitutions *)
Accumulate[Prepend[Flatten[Nest[Flatten[# /. {0 -> {1, 1}, 1 -> {1, 0}}] &, {0}, 7] /. Thread[{0, 1} -> {{5, 5}, {6, 4}}]], 3]]
(* Peter J. C. Moses, May 01 2018 *)
********
(* Sequence "a" via Hofstadter substitutions; see his 2014 link *)
morph = Rest[Nest[Flatten[#/.{1->{3},3->{1,1,3}}]&,{1},6]]
hoff = Accumulate[Prepend[Flatten[morph/.Thread[{1,3}->{{6,4,5,5},{6,4,6,4,6,4,5,5}}]],3]]
(* Peter J. C. Moses, May 01 2018 *)

def aupton(nn):
    alst, disallowed, mink = [0], {0}, 1
    for n in range(1, nn+1):
        nextk = mink + 1
        while nextk in disallowed: nextk += 1
        an = mink + nextk
        alst.append(an)
        disallowed.update([mink, nextk, an])
        mink = nextk + 1
        while mink in disallowed: mink += 1
    return alst
print(aupton(57)) # Michael S. Branicky, Jan 31 2022

def A075326(n): return 5*n-1-int((n|(~((m:=n-1>>1)+1)&m).bit_length())&1) if n else 0 # Chai Wah Wu, Sep 11 2024

See Zaslavsky (2016) link.

More terms from David Wasserman, Jan 16 2005

Entry revised (including the addition of an initial 0) by N. J. A. Sloane, Oct 26 2014 and Sep 26 2016 (following a suggestion from Thomas Zaslavsky)

A080426 a(1)=1, a(2)=3; all terms are either 1 or 3; each run of 3's is followed by a run of two 1's; and a(n) is the length of the n-th run of 3's.

Original entry on oeis.org

1, 3, 1, 1, 3, 3, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 3, 3, 1, 1, 3, 3, 3, 1, 1, 3, 3, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 3, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 3, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 3, 3, 1, 1, 3, 3, 3, 1, 1, 3, 3, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 3, 3, 1, 1, 3, 3, 3, 1, 1, 3, 3, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 3, 3, 1, 1

Offset: 1

John W. Layman, Feb 18 2003

nonn

It appears that the sequence can be calculated by any of the following three methods: (1) Start with 1 and repeatedly replace (simultaneously) all 1's with 1,3,1 and all 3's with 1,3,3,3,1. [Equivalently, trajectory of 1 under the morphism 1 -> 1,3,1; 3 -> 1,3,3,3,1. - N. J. A. Sloane, Nov 03 2019] (2) a(n)= A026490(2n). (3) Replace each 2 in A026465 (run lengths in Thue-Morse) with 3.
Length of n-th run of 1's in the Feigenbaum sequence A035263 = 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, .... - Philippe Deléham, Apr 18 2004
Another construction. Let S_0 = 1, and let S_n be obtained by applying the morphism 1 -> 3, 3 -> 113 to S_{n-1}. The sequence is the concatenation S_0, S_1, S_2, ... - D. R. Hofstadter, Oct 23 2014
a(n+1) is the number of times n appears in A003160. - John Keith, Dec 31 2020

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Jean-Paul Allouche, On the morphism 1 -> 121, 2 -> 12221, CNRS France, 2024. See pp. 5-6.
Jean-Paul Allouche, On the morphism 1 -> 121, 2 -> 12221, Preprint, 2024 [Local copy, with permission]
D. R. Hofstadter, Anti-Fibonacci numbers, Oct 23 2014.

Cf. A026465, A026490, A035263, A003156, A328979, A003160.

Arises in the analysis of A075326, A249031 and A249032.

-- following Deléham
import Data.List (group)
a080426 n = a080426_list !! n
a080426_list = map length $ filter ((== 1) . head) $ group a035263_list
-- Reinhard Zumkeller, Oct 27 2014

Position[ Nest[ Flatten[# /. {0 -> {0, 2, 1}, 1 -> {0}, 2 -> {0}}]&, {0}, 8], 0] // Flatten // Differences // Prepend[#, 1]& (* Jean-François Alcover, Mar 14 2014, after Philippe Deléham *)
nsteps=7;Flatten[SubstitutionSystem[{1->{3},3->{1,1,3}},{1},nsteps]] (* Paolo Xausa, Aug 12 2022, using D. R. Hofstadter's construction *)

A080426(nmax) = my(a=[1], s=[[1, 3, 1], [], [1, 3, 3, 3, 1]]); while(length(a)A080426(100) \\ Paolo Xausa, Sep 14 2022, using method (1) from comments

def A080426(nmax):
    a, s = "1", "".maketrans({"1":"131", "3":"13331"})
    while len(a) < nmax: a = a.translate(s)
    return list(map(int, a[:nmax]))
print(A080426(100)) # Paolo Xausa, Aug 30 2022, using method (1) from comments

def A080426(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        kmin = kmax >> 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def f(x):
        c, s = x, bin(x)[2:]
        l = len(s)
        for i in range(l&1,l,2):
            c -= int(s[i])+int('0'+s[:i],2)
        return c
    return bisection(lambda x:f(x)+n,n,n)-bisection(lambda x:f(x)+n-1,n-1,n-1)-1 # Chai Wah Wu, Jan 29 2025

a(1) = 1; for n>1, a(n) = A003156(n) - A003156(n-1). - Philippe Deléham, Apr 16 2004

A101544 Smallest permutation of the natural numbers with a(3k-2) + a(3k-1) = a(3*k), k > 0.

Original entry on oeis.org

1, 2, 3, 4, 5, 9, 6, 7, 13, 8, 10, 18, 11, 12, 23, 14, 15, 29, 16, 17, 33, 19, 20, 39, 21, 22, 43, 24, 25, 49, 26, 27, 53, 28, 30, 58, 31, 32, 63, 34, 35, 69, 36, 37, 73, 38, 40, 78, 41, 42, 83, 44, 45, 89, 46, 47, 93, 48, 50, 98, 51, 52, 103, 54, 55, 109, 56, 57, 113, 59, 60

Offset: 1

Reinhard Zumkeller, Dec 06 2004

nonn

Inverse: A101545; A101546(n) = a(a(n)).
From Bernard Schott, Jun 30 2019: (Start)
The terms can also be written simply following this array with 3 columns:
   1st column       2nd column          3rd column
        1      +        2          =         3
        4      +        5          =         9
        6      +        7          =        13
        8      +       10          =        18
       11      +       12          =        23
       14      +       15          =        29
       16      +       17          =        33
       ...             ...                  ...
Question: in which column ends up the repdigit R_m(d) with m times the digit d?
Answer: R_m(d) will be in:
1) column 1 if d = 1, 4, 6, 8, or if d = 9 and m is even;
2) column 2 if d = 2, 5, 7;
3) column 3 if d = 3, or if d = 9 and m is odd.
Problem coming from Krusemeyer et al. (End)

Ivan Neretin, Table of n, a(n) for n = 1..10000
Mark I. Krusemeyer, George T. Gilbert, Loren C. Larson, A Mathematical Orchard, Problems and Solutions, MAA, 2012, Problem 99, pp. 179-181.
Index entries for sequences that are permutations of the natural numbers

Cf. A075326, A249031.

N:= 100: # to get a(1) .. a(N)
S:= {$1..N}:
for n from 1 to N do
  if n mod 3 = 0 then A[n] := A[n-1]+A[n-2]
  else A[n]:= min(S)
  fi;
  S:= S minus {A[n]};
od:
seq(A[i],i=1..N); # Robert Israel, Feb 07 2016

Fold[Append[#1, If[Divisible[#2, 3], #1[[-1]] + #1[[-2]], Min@Complement[Range[Max@#1 + 1], #1]]] &, {1}, Range[2, 71]] (* Ivan Neretin, Feb 05 2016 *)

A101544_upto(N, U=[], T=0)=vector(N, n, if(n%=3, while(if(U, U[1])==T+=1, U=U[^1]); n>1 || N=T; T, U=concat(U, N+=T); N))
apply( {A101544(n, k=(n-=1)\12, m=n\3%4, c=n%3)=(10*k+3*m-(m>1))<<(c>1)+c+(m<3 || c==1 || valuation(k+1,2)%2)}, [1..99]) \\ M. F. Hasler, Nov 26 2024

From Rémy Sigrist, Apr 05 2020: (Start)
- a(3*n-2) = A249031(2*n-1),
- a(3*n-1) = A249031(2*n),
- a(3*n)   = A075326(n).
(End)
a(3*(4k + m) + c) = (10k + 3m - [m>1])*2^[c=3] + c - [m = 3 and c <> 2 and k+1 is in A036554], where 1 <= c <= 3, 0 <= m <= 3, and [.] is the Iverson bracket. - M. F. Hasler, Nov 26 2024

A249032 First differences of A075326.

Original entry on oeis.org

3, 6, 4, 5, 5, 6, 4, 6, 4, 6, 4, 5, 5, 6, 4, 5, 5, 6, 4, 5, 5, 6, 4, 6, 4, 6, 4, 5, 5, 6, 4, 6, 4, 6, 4, 5, 5, 6, 4, 6, 4, 6, 4, 5, 5, 6, 4, 5, 5, 6, 4, 5, 5, 6, 4, 6, 4, 6, 4, 5, 5, 6, 4, 5, 5, 6, 4, 5, 5, 6, 4, 6, 4, 6, 4, 5, 5, 6, 4, 5, 5, 6, 4, 5, 5, 6

Offset: 0

N. J. A. Sloane, Oct 26 2014

nonn

Can be constructed as follows. Apart from the initial "3", one always has either "6-4" (i.e., a 6 followed by a 4), or else "5-5". The 6-4's always come either alone (6-4) or triply (6-4, 6-4, 6-4), while the 5-5's always come alone. So if we let "6-4, 5-5" be represented by the numeral "1", and "6-4, 6-4, 6-4, 5-5" by the numeral "3", then the sequence of first differences, in this compressed code, is A080426, which itself is defined by a simple substitution rule. - D. R. Hofstadter, Oct 23 2014

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Robbert Fokkink and Gandhar Joshi, Anti-recurrence sequences, arXiv:2506.13337 [math.NT], 2025. See pp. 2, 18.
D. R. Hofstadter, Anti-Fibonacci numbers, Oct 23 2014
Thomas Zaslavsky, Anti-Fibonacci Numbers: A Formula, Sep 26 2016

Cf. A075326, A080426, A249031.

a249032 n = a249032_list !! n
a249032_list = zipWith (-) (tail a075326_list) a075326_list
-- Reinhard Zumkeller, Oct 26 2014

def A249032(n): return 4+int((n+1|(~((m:=n>>1)+1)&m).bit_length())&1^1)+int((n|(~((k:=n-1>>1)+1)&k).bit_length())&1) if n else 3 # Chai Wah Wu, Sep 11 2024

A332787 Negative-pan primes (see Comments).

Original entry on oeis.org

2, 3, 7, 11, 13, 17, 19, 23, 29, 37, 41, 43, 47, 53, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 227, 229, 233, 239, 241, 251, 257, 263, 277, 281, 283, 293, 307, 311, 317, 331, 337, 347, 349, 353, 359, 367

Offset: 1

Ivan N. Ianakiev, Feb 24 2020

Take a double-pan balance scale and name the pans "negative" and "positive". At each step, the question is: "Is there an unused prime that would balance the scale if added to the positive pan?" If the answer is yes, add that prime to the positive pan. Otherwise, add the smallest unused prime to the negative pan.

The negative pan N can be fractalized, i.e., subdivided into NN and NP pans, where NN ={{2,3,7,11},{13,17,19,29,37,41,43},...} and NP = {{23},{199},...}. Can this fractalization be continued infinitely?

			First division: 2 and 3 unbalance the scale (and go to the negative pan N), but 5 = 2 + 3 balances it (and goes to the positive pan P).
Second division: 2,3,7 and 11 unbalance the N pan (and go to the NN subpan), but 23 balances it (and goes to NP subpan).

Michael S. Branicky, Table of n, a(n) for n = 1..10000

Cf. A249031, A332341, A332788.

a[1]=-2;
a[n_]:=a[n]=Module[{tab=Table[a[i],{i,1,n-1}],
totalN=Abs[Total[Select[Table[a[i],{i,1,n-1}],Negative]]],
totalP=Total[Select[Table[a[i],{i,1,n-1}],Positive]],
l=NextPrime[Last[Select[Table[a[i],{i,1,n-1}],Negative]],-1]},
If[ totalN==totalP,
If[ PrimePi[tab[[-1]]]-PrimePi[Abs[tab[[-2]]]]==1,-NextPrime[tab[[-1]]],
NextPrime[tab[[-2]],-1]],
If[PrimeQ[totalN-totalP]&&FreeQ[Abs[tab],totalN-totalP],totalN-totalP,
If[FreeQ[Abs[tab], Abs[l]], l, While[!FreeQ[Abs[tab],Abs[l]],l=NextPrime[l,-1]];l]
]]];Abs[Select[a/@Range[78],Negative]]

from itertools import islice
from sympy import isprime, nextprime
def agen(): # generator of terms
    used, d, nextp = set(), 0, 2
    while True:
        if d > 0 and d not in used and isprime(d):
            used.add(d); d = 0
        while nextp in used:
            nextp = nextprime(nextp)
        used.add(nextp); yield nextp; d += nextp
print(list(islice(agen(), 65))) # Michael S. Branicky, May 12 2022

cp's OEIS Frontend

A075326 Anti-Fibonacci numbers: start with a(0) = 0, and extend by the rule that the next term is the sum of the two smallest numbers that are not in the sequence nor were used to form an earlier sum.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Python

Python

Formula

Extensions

A080426 a(1)=1, a(2)=3; all terms are either 1 or 3; each run of 3's is followed by a run of two 1's; and a(n) is the length of the n-th run of 3's.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Python

Python

Formula

A101544 Smallest permutation of the natural numbers with a(3*k-2) + a(3*k-1) = a(3*k), k > 0.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A249032 First differences of A075326.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Python

A332787 Negative-pan primes (see Comments).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

A101544 Smallest permutation of the natural numbers with a(3k-2) + a(3k-1) = a(3*k), k > 0.