A074890 a(n) is the action of recursively applying 'Rule 30' elementary cellular automata on the binary representation of n if the cells may only expand into the significant bit, a(0) = 1.

1, 3, 6, 13, 25, 55, 100, 222, 401, 891, 1602, 3559, 6428, 14258, 25647, 56936, 102860, 228154, 410339, 910998, 1645813, 3650437, 6565453, 14576121, 26332935, 58407052, 105047514, 233217299, 421327294, 934513441, 1680759539, 3731477134, 6741237465, 14952214679

Offset

0,2

Comments

Previous name: Decimal form of binary integers produced by a modified version of Wolfram's Rule 30 one-dimensional cellular automaton.

According to the common nomenclature (see A110240), this is actually a Rule 86 for all but the least-significant bit, and a Rule 252 for the least-significant bit, because the (fractional) bits right from the binary dot are never set. As a side effect, the first 11 terms--not the 12th--can be reproduced by a(n)=floor(A110240(n)/2^n). - R. J. Mathar, Apr 29 2009

The out-of-bounds cell on the least significant bit's edge is taken to be 0. - Mia Boudreau, Sep 10 2025

References

S. Wolfram, A New Kind of Science, Wolfram Media Inc., (2002), p. 27.

Links

Mia Boudreau, Table of n, a(n) for n = 0..1800

Eric Weisstein's World of Mathematics, Rule 30

The Wolfram Atlas of Simple Programs, Rule 30

Formula

a(n+1) = A387312(a(n)). - Mia Boudreau, Sep 10 2025

Example

Initial terms:
  1 (1)
  11 (3)
  110 (6)
  1101 (13)
  11001 (25)
  110111 (55)

Mathematica

NestList[BitXor[BitOr[#, 2*#], Quotient[#, 2]] &, 1, 35] (* Paolo Xausa, May 20 2026 *)

Prog

(Java)
BigInteger a(int n){
 BigInteger k = BigInteger.ONE;
 for(int t = 0; t < n; t++){
  int RULE = 30;
  BigInteger x = BigInteger.ZERO;
  for(int i = 0; i < n+1; i++)
   if((RULE>>((gb(k, i+1)<<2)|(gb(k, i)<<1)|gb(k, i-1))&1)>0) x=x.setBit(i);
  k = x; }
 return k; }
int gb(BigInteger b, int i){return b.shiftRight(i).testBit(0)?1:0; } // Mia Boudreau, Sep 10 2025

Crossrefs

Cf. A110240, A387312, A269160 for Rule 30.

Sequence in context: A005116 A121349 A215984 * A244704 A032198 A079941

Adjacent sequences: A074887 A074888 A074889 * A074891 A074892 A074893

Keyword

base,nonn

Author

Jason E Sackett (jason(AT)heavyion.com), Sep 13 2002

Extensions

Definition modified by N. J. A. Sloane, Jul 28 2014

Entry revised by Mia Boudreau, Sep 11 2025

Status

approved