Jacob A. Siehler - cp's OEIS frontend

A199770 Self-convolution with "addition" played by bitwise XOR.

1, 0, 2, 6, 18, 50, 146, 426, 1282, 3810, 11394, 34082, 102338, 306658, 919874, 2759154, 8276898, 24828386, 74484386, 223444258, 670326242, 2010964770, 6032902242, 18098635298, 54295809826, 162887261410, 488661978274, 1465985458850, 4397955924386

Offset: 1

Jacob A. Siehler, Nov 10 2011

Reinhard Zumkeller, Table of n, a(n) for n = 1..1000

Cf. A000108 (Catalan numbers).

Cf. A007462, A192484.

import Data.Bits (xor)
a199770 n = a199770_list !! (n-1)
a199770_list = 1 : f [1] where
   f xs = y : f (y : xs) where
     y = sum $ zipWith xor xs $ reverse xs :: Integer
-- Reinhard Zumkeller, Jul 15 2012

a:= proc(n) option remember; `if`(n=0, 1, add(
      Bits[Xor](a(i), a(n-1-i)), i=0..n-1))
    end:
seq(a(n), n=0..35);  # Alois P. Heinz, Jun 16 2018

a[1] = 1; a[n_] := a[n] = Sum[BitXor[a[i], a[n - i]], {i, 1, n - 1}]; Table[a[n], {n, 30}]

a(1)=1, a(n) = sum ( a(i) XOR a(n-i), i = 1 .. n-1).

A180125 Self-convolution of period-doubling sequence A035263.

Original entry on oeis.org

0, 1, 0, 2, 2, 3, 2, 5, 2, 5, 2, 6, 4, 7, 4, 10, 6, 9, 6, 12, 8, 11, 8, 15, 8, 13, 8, 16, 10, 15, 10, 21, 10, 17, 10, 20, 12, 19, 12, 25, 12, 21, 12, 24, 14, 23, 14, 30, 16, 25, 16, 30, 18, 27, 18, 35, 18, 29, 18, 34, 20, 31, 20, 42, 22, 33, 22, 40, 24, 35, 24, 45, 24, 37

Offset: 1

Jacob A. Siehler, Aug 11 2010

nonn

Reducing a(n) mod 2 gives 1-A035263(n), which is also A096268(n+1).

Cf. A035263, A096268

b[i_] := b[i] = If[OddQ[i], 1, 1 - b[i/2]]; a[n_] := Sum[b[i] b[n - i], {i, 1, n - 1}]

a(n) = sum(b(i)b(n-i), i=1..(n-1)), where b(i)=A035263(i).

A178752 a(n) gives the number of conjugacy classes in the permutation group generated by transposition (1 2) and double n-cycle (1 3 5 7 ... 2n-1)(2 4 6 8 ... 2n). This group is a semidirect product formed by a cyclic group acting on an elementary abelian 2-group of rank n by cyclically permuting the factors.

Original entry on oeis.org

2, 5, 8, 13, 16, 28, 32, 56, 80, 136, 208, 400, 656, 1232, 2240, 4192, 7744, 14728, 27632, 52664, 99968, 190984, 364768, 699760, 1342256, 2582120, 4971248, 9588880, 18512848, 35795104, 69273728, 134224064, 260301632, 505301920, 981707008

Offset: 1

Jacob A. Siehler, Jun 09 2010

G. C. Greubel, Table of n, a(n) for n = 1..1000
J. A. Siehler, The Finite Lamplighter Groups: A Guided Tour, College Mathematics Journal, Vol. 43, No. 3 (May 2012), pp. 203-211. - From _N. J. A. Sloane_, Oct 05 2012

a[n_]:= Sum[(1/GCD[n,k])2^s EulerPhi[GCD[n,k]/s], {k, 0, n-1}, {s, Divisors[GCD[n,k]]}];

a(n) = Sum_{k=0..n-1} ( 1/gcd(n,k) 2^s phi(gcd(n,k)/s), s in divisors(gcd(n,k)) ).

More terms from Robert G. Wilson v, Jun 10 2010

A171503 Number of 2 X 2 integer matrices with entries from {0,1,...,n} having determinant 1.

Original entry on oeis.org

0, 3, 7, 15, 23, 39, 47, 71, 87, 111, 127, 167, 183, 231, 255, 287, 319, 383, 407, 479, 511, 559, 599, 687, 719, 799, 847, 919, 967, 1079, 1111, 1231, 1295, 1375, 1439, 1535, 1583, 1727, 1799, 1895, 1959, 2119, 2167, 2335, 2415, 2511, 2599

Offset: 0

Jacob A. Siehler, Dec 10 2009

nonn

Number of distinct solutions to k*x+h=0, where |h|<=n and k=1,2,...,n. - Giovanni Resta, Jan 08 2013.

Number of reduced rational numbers r/s with |r|<=n and 0Juan M. Marquez, Apr 13 2015

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Cf. A062801, A000010, A018805. Differences are A002246.

See A326354 for an essentially identical sequence.

with(numtheory):
a:= proc(n) option remember;
       `if`(n<2, [0, 3][n+1], a(n-1) + 4*phi(n))
    end:
seq(a(n), n=0..60);

a[n_]:=Count[Det/@(Partition[ #,2]&/@Tuples[Range[0,n],4]),1]
(* Second program: *)
a[0] = 0; a[1] = 3; a[n_] := a[n] = a[n-1] + 4*EulerPhi[n];
Table[a[n], {n, 0, 60}] (* Jean-François Alcover, Jun 16 2018 *)

a(n)=(n>0)+2*sum(k=1, n, moebius(k)*(n\k)^2) \\ Charles R Greathouse IV, Apr 20 2015

from functools import lru_cache
@lru_cache(maxsize=None)
def A171503(n): # based on second formula in A018805
    if n == 0:
        return 0
    c, j = 0, 2
    k1 = n//j
    while k1 > 1:
        j2 = n//k1 + 1
        c += (j2-j)*(A171503(k1)-1)//2
        j, k1 = j2, n//j2
    return 2*(n*(n-1)-c+j) - 1 # Chai Wah Wu, Mar 25 2021

Recursion: a(n) = a(n - 1) + 4*phi(n) for n > 1, with phi being Euler's totient function. - Juan M. Marquez, Jan 19 2010

a(n) = 4 * A002088(n) - 1 for n >= 1. - Robert Israel, Jun 01 2014

Edited by Alois P. Heinz, Jan 19 2011

A159277 Ways to write the identity as a product of n 3-cycles in symmetric group S_4.

Original entry on oeis.org

1, 0, 8, 32, 384, 2560, 22528, 172032, 1409024, 11141120, 89653248, 715128832, 5729419264, 45801799680, 366548615168, 2931852050432, 23456963887104, 187647121162240, 1501211329036288, 12009553193336832, 96076975302508544

Offset: 0

Jacob A. Siehler, Apr 07 2009

Flavien Mabilat, Some counting formulas for λ-quiddities over the rings Z / 2^m Z, arXiv:2402.09968 [math.CO], 2024.

Cf. A091904.

a(n+1) = (2/3)*(-1)^n*((-8)^n-4^n).
O.g.f.: 1 - 8*x^2/(32*x^2+4*x-1).
a(n) = 8 * A091904(n-1). - R. J. Mathar, Jun 28 2009

Offset corrected by R. J. Mathar, Jun 28 2009

Offset changed back and a(0) = 1 prepended by Andrey Zabolotskiy, Feb 21 2024

A137619 a(n) is the maximal (nonredundant) number of switch flippings in a solution of the all-ones lights out problem on an n X n square.

Original entry on oeis.org

1, 4, 5, 12, 15, 28, 33, 40, 55, 44, 71, 72, 105, 96, 117, 152, 147, 188, 225, 224, 245, 276, 299, 306, 353, 356, 405, 416, 451

Offset: 1

Jacob A. Siehler, Apr 27 2008

See A075462 for references.

Cf. A075464.

A134968 Number of convex functions from {1,...,n} to itself.

Original entry on oeis.org

1, 1, 4, 16, 54, 168, 462, 1212, 2937, 6832, 15135, 32430, 66898, 134710, 263466, 504308, 944208, 1736575, 3134832, 5574947, 9760954, 16868418, 28771587, 48513127, 80867486, 133455462, 218041708, 353039664, 566580113, 901958971, 1424480451, 2233367056

Offset: 0

Jacob A. Siehler, Feb 04 2008, Feb 06 2008

That is, the number of sequences of length n, taking values in {1,...,n} that have nondecreasing first differences (nonnegative second differences).

			a(3)=16: the 16 sequences are 111, 112, 113, 123, 211, 212, 213, 222, 223, 311, 312, 313, 321, 322, 323 and 333.

(*P[n,k]=number of ways to partition n into exactly k parts*) P[n_Integer, n_Integer] = 1; P[n_Integer, k_Integer] := P[n, k] = Sum[P[n - k, r], {r, 1, Min[n - k, k]}]
(*q[n,k]=number of ways to partition n into k-or-fewer parts*) q[0, 0] = 1; q[n_Integer, 0] = 0; q[n_Integer, k_Integer] := q[n, k] = q[n, k - 1] + P[n, k]
a[n_] := Sum[(n - Max[f, r])*P[r, s]*q[f, n - 1 - s], {r, 0, n - 1}, {s, 0, n - 1}, {f, 0, n - 1}]

See Mathematica code.

A135342 Number of distinct means of nonempty subsets of {1,...,n}.

Original entry on oeis.org

1, 3, 5, 9, 15, 25, 37, 55, 77, 105, 137, 179, 225, 283, 347, 419, 499, 595, 697, 817, 945, 1085, 1235, 1407, 1587, 1787, 1999, 2229, 2471, 2741, 3019, 3327, 3651, 3995, 4355, 4739, 5135, 5567, 6017, 6491, 6981, 7511, 8053, 8637, 9241, 9869, 10519, 11215, 11927, 12681

Offset: 1

Jacob A. Siehler, Feb 16 2008

			a(4) = 9: the possible means for a set drawn from {1, 2, 3, 4} are {1, 3/2, 2, 7/3, 5/2, 8/3, 3, 7/2, 4}.

Alois P. Heinz, Table of n, a(n) for n = 1..10000
R. J. Mathar, Derivation of formula for 2nd differences

First differences are A002088, second differences A000010.

a:= proc(n) option remember; `if`(n<4, [0, 1, 3, 5][n+1],
      2*a(n-1)-a(n-2)+numtheory[phi](n-1))
    end:
seq(a(n), n=0..50);  # Alois P. Heinz, Sep 13 2019

a[n_] := Sum[EulerPhi[k] (n - k), {k, 1, n - 1}] + Min[n, 2]

M135342=List([1,3,5]);
A135342(n)=while(n>#M135342, listput(M135342, [-1,2]*Col(M135342[-2..-1])+eulerphi(#M135342))); M135342[n];
apply(A135342, [1..55]) \\ M. F. Hasler, Jan 24 2023

from sympy import totient
def A135342(n, A=[1,3,5]):
    while n>len(A): A.append(2*A[-1]-A[-2]+totient(len(A)))
    return A[n-1] # M. F. Hasler, Jan 24 2023

a(n) = Sum_{k=1..n-1} [(n-k) * phi(k)] + min(n,2) = A103116(n-1)+ min(n,2); a(1)=1; a(2)=3; a(3)=5.
a(n) = 2*a(n-1) - a(n-2) + phi(n-1) for n>3.
a(n)-a(n-1) = A002088(n-1), n>=3. (Note the previous formula just says that the 2nd differences are A000010, and this is a trivial consequence.) - R. J. Mathar, Jan 27 2023

A128975 a(n) = the number of unordered triples of integers (a,b,c) with a+b+c=n, whose bitwise XOR is zero. Equivalently, the number of three-heap nim games with n stones which are in a losing position for the first player.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 4, 0, 0, 0, 1, 0, 1, 0, 4, 0, 1, 0, 4, 0, 4, 0, 13, 0, 0, 0, 1, 0, 1, 0, 4, 0, 1, 0, 4, 0, 4, 0, 13, 0, 1, 0, 4, 0, 4, 0, 13, 0, 4, 0, 13, 0, 13, 0, 40, 0, 0, 0, 1, 0, 1, 0, 4, 0, 1, 0, 4, 0, 4, 0, 13, 0, 1, 0, 4, 0, 4, 0, 13, 0, 4, 0, 13, 0, 13, 0, 40, 0, 1, 0, 4, 0, 4, 0

Offset: 1

Jacob A. Siehler, Apr 29 2007

The following sequences all appear to have the same parity: A003071, A029886, A061297, A092524, A093431, A102393, A104258, A122248, A128975. - Jeremy Gardiner, Dec 28 2008

			For example, a(14)=4; the four 3-tuples are (1,6,7), (2,5,7), (3,4,7) and (3,5,6).

Antti Karttunen, Table of n, a(n) for n = 1..65537
Tanya Khovanova, There are no coincidences, arXiv preprint 1410.2193 [math.CO], 2014.

Cf. A000120, A003987.

A128975(n) = if(n%2,0,(1/2)*((3^(hammingweight(n)-1))-1)); \\ Antti Karttunen, Sep 25 2018

a(n)=0 if n is odd; otherwise, a(n) = ( 3^(r-1) - 1)/2, where r is the number of 1's in the binary expansion of n.

A121016 Numbers whose binary expansion is properly periodic.

Original entry on oeis.org

3, 7, 10, 15, 31, 36, 42, 45, 54, 63, 127, 136, 153, 170, 187, 204, 221, 238, 255, 292, 365, 438, 511, 528, 561, 594, 627, 660, 682, 693, 726, 759, 792, 825, 858, 891, 924, 957, 990, 1023, 2047, 2080, 2145, 2184, 2210, 2275, 2340, 2405, 2457, 2470, 2535

Offset: 1

Jacob A. Siehler, Sep 08 2006

A finite sequence is aperiodic if its cyclic rotations are all different. - Gus Wiseman, Oct 31 2019

			For example, 204=(1100 1100)_2 and 292=(100 100 100)_2 belong to the sequence, but 30=(11110)_2 cannot be split into repeating periods.
From _Gus Wiseman_, Oct 31 2019: (Start)
The sequence of terms together with their binary expansions and binary indices begins:
   3:         11 ~ {1,2}
   7:        111 ~ {1,2,3}
   10:      1010 ~ {2,4}
   15:      1111 ~ {1,2,3,4}
   31:     11111 ~ {1,2,3,4,5}
   36:    100100 ~ {3,6}
   42:    101010 ~ {2,4,6}
   45:    101101 ~ {1,3,4,6}
   54:    110110 ~ {2,3,5,6}
   63:    111111 ~ {1,2,3,4,5,6}
  127:   1111111 ~ {1,2,3,4,5,6,7}
  136:  10001000 ~ {4,8}
  153:  10011001 ~ {1,4,5,8}
  170:  10101010 ~ {2,4,6,8}
  187:  10111011 ~ {1,2,4,5,6,8}
  204:  11001100 ~ {3,4,7,8}
  221:  11011101 ~ {1,3,4,5,7,8}
  238:  11101110 ~ {2,3,4,6,7,8}
  255:  11111111 ~ {1,2,3,4,5,6,7,8}
  292: 100100100 ~ {3,6,9}
(End)

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

A020330 is a subsequence.
Numbers whose binary expansion is aperiodic are A328594.
Numbers whose reversed binary expansion is Lyndon are A328596.
Numbers whose binary indices have equal run-lengths are A164707.
Cf. A000120, A003714, A014081, A065609, A069010, A275692, A328595.

PeriodicQ[n_, base_] := Block[{l = IntegerDigits[n, base]}, MemberQ[ RotateLeft[l, # ] & /@ Most@ Divisors@ Length@l, l]]; Select[ Range@2599, PeriodicQ[ #, 2] &]

is(n)=n=binary(n);fordiv(#n,d,for(i=1,#n/d-1, for(j=1,d, if(n[j]!=n[j+i*d], next(3)))); return(d<#n)) \\ Charles R Greathouse IV, Dec 10 2013

cp's OEIS Frontend

User: Jacob A. Siehler

A199770 Self-convolution with "addition" played by bitwise XOR.

Views

Author

Keywords

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Formula

A180125 Self-convolution of period-doubling sequence A035263.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

Views

Author

Keywords

Links

Programs

Mathematica

Formula

Extensions

A171503 Number of 2 X 2 integer matrices with entries from {0,1,...,n} having determinant 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A159277 Ways to write the identity as a product of n 3-cycles in symmetric group S_4.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A137619 a(n) is the maximal (nonredundant) number of switch flippings in a solution of the all-ones lights out problem on an n X n square.

Views

Author

Keywords

References

Crossrefs

A134968 Number of convex functions from {1,...,n} to itself.

Views

Author

Keywords

Comments

Examples

Programs

Mathematica

Formula

A135342 Number of distinct means of nonempty subsets of {1,...,n}.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula