A004277 -id:A004277 - cp's OEIS frontend

A356148 a(n) is the number of positive integers whose binary expansion appears as a substring in the binary expansion of n or its complement.

1, 2, 2, 4, 3, 4, 3, 6, 6, 4, 6, 6, 6, 6, 4, 8, 9, 9, 8, 8, 5, 9, 9, 9, 8, 8, 9, 9, 9, 8, 5, 10, 12, 13, 12, 12, 12, 10, 12, 12, 12, 6, 10, 12, 12, 13, 12, 12, 12, 12, 10, 12, 10, 12, 13, 12, 12, 12, 13, 12, 12, 10, 6, 12, 15, 17, 16, 17, 17, 16, 15, 17, 15

Offset: 1

Rémy Sigrist, Jul 28 2022

Leading 0's in binary expansions are ignored.

			For n = 43:
- the binary expansion of 43 is "101011",
- it contains the positive numbers with binary expansions "1", "10", "11", "101", "1010", "1011", "10101", "101011",
- the complement of "101011" is "010100",
- it contains the positive numbers with binary expansions "1", "10", "100", "101", "1010", "10100",
- all in all, we have the following substrings: "1", "10", "11", "100", "101", "1010", "1011", "10100", "10101", "101011",
- so a(43) = 10.

Rémy Sigrist, Table of n, a(n) for n = 1..8192
Index entries for sequences related to binary expansion of n

Cf. A004277, A122953, A356149, A356150.

a(n) = { my (b=binary(n)); #setbinop((i,j) -> my (s=fromdigits(b[i..j], 2)); if (b[i], s, 2^(j-i+1)-1-s), [1..#b]) }

def a(n):
    N = n.bit_length()
    c, s = ((1<> i)
            s.add((mask&c) >> i)
    return len(s - {0})
print([a(n) for n in range(1, 74)]) # Michael S. Branicky, Jul 28 2022

a(n) >= A122953(n).
a(2^k-1) = 2^k-1 for any k >= 0.
a(2^k) = A004277(k) for any k >= 0.

A084859 Binomial transform of Cullen numbers A002064.

Original entry on oeis.org

1, 4, 16, 62, 232, 842, 2980, 10334, 35248, 118610, 394684, 1301126, 4255624, 13825658, 44657428, 143521838, 459230560, 1463719586, 4649308012, 14722502870, 46491507256, 146447041994, 460259735236, 1443537130622

Offset: 0

Paul Barry, Jun 12 2003

Index entries for linear recurrences with constant coefficients, signature (8,-21,18).

Cf. A004277.

LinearRecurrence[{8,-21,18},{1,4,16},30] (* Harvey P. Dale, Mar 31 2015 *)

a(n)=2^n+2n*3^(n-1); a(n)=sum{k=0..n, C(n, k)(1+k*2^k) }.
O.g.f.: (1-4x+5x^2)/[(1-2x)(-1+3x)^2]. - R. J. Mathar, Apr 02 2008
a(0)=1, a(1)=4, a(2)=16, a(n)=8*a(n-1)-21*a(n-2)+18*a(n-3). - Harvey P. Dale, Mar 31 2015

A086460 Square array read by antidiagonals: T(n,k)=nk+0^n.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 2, 0, 1, 3, 4, 3, 0, 1, 4, 6, 6, 4, 0, 1, 5, 8, 9, 8, 5, 0, 1, 6, 10, 12, 12, 10, 6, 0, 1, 7, 12, 15, 16, 15, 12, 7, 0, 1, 8, 14, 18, 20, 20, 18, 14, 8, 0, 1, 9, 16, 21, 24, 25, 24, 21, 16, 9, 0, 1, 10, 18, 24, 28, 30, 30, 28, 24, 18, 10, 0, 1, 11, 20, 27, 32, 35, 36

Offset: 0

Paul Barry, Jul 21 2003

Rows include A028310, A004277, A008486, A008574, A008706, A008458. Main diagonal is n^2+0^n (A000290, preceded by extra 1). Inverse binomial transform of array A049513.

			Rows begin
1 0 0 0 0 ...
1 1 2 3 4 ...
1 2 4 6 8 ...
1 3 6 9 12 ...
1 4 8 12 16 ...

T(n, k)=nk+0^n

A113322 First differences of A113321.

Original entry on oeis.org

1, 2, -1, 3, -1, 4, -2, 5, -4, 6, -4, 7, -6, 8, -6, 9, -7, 10, -9, 11, -9, 12, -10, 13, -12, 14, -12, 15, -14, 16, -14, 17, -15, 18, -17, 19, -17, 20, -19, 21, -19, 22, -20, 23, -22, 24, -22, 25, -23, 26, -25, 27, -25, 28, -27, 29, -27, 30, -28, 31, -30, 32, -30, 33, -31, 34

Offset: 1

Reinhard Zumkeller, Oct 26 2005

sign

a(n) = A113321(n+1) - A113321(n);

A000027 is a subsequence: a(A004277(n-1)) = n.

A129687 A129686 * A007318.

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 2, 4, 3, 1, 2, 6, 7, 4, 1, 2, 8, 13, 11, 5, 1, 2, 10, 21, 24, 16, 6, 1, 2, 12, 31, 45, 40, 22, 7, 1, 2, 14, 43, 76, 85, 62, 29, 8, 1, 2, 16, 57, 119, 161, 147, 91, 37, 9, 1, 2, 18, 73, 176, 280, 308, 238, 128, 46, 10, 1, 2, 20, 91, 249, 456

Offset: 0

Gary W. Adamson, Apr 28 2007

Row sums = A084215: (1, 2, 5, 10, 20, 40, 80, ...). A007318 * A129686 = A124725.
From Philippe Deléham, Feb 12 2014: (Start)
Riordan array ((1+x^2)/(1-x), x/(1-x)).
Diagonal sums are A000032(n) - 0^n (cf. A000204).
T(n,0) = A046698(n+1).
T(n+1,1) = A004277(n).
T(n+2,2) = A002061(n+1).
T(n+3,3) = A006527(n+1) = A167875(n).
T(n+4,4) = A006007(n+1).
T(n+5,5) = A081282(n+1). (End)

			First few rows of the triangle:
  1;
  1,   1;
  2,   2,   1;
  2,   4,   3,   1;
  2,   6,   7,   4,   1;
  2,   8,  13,  11,   5,   1;
  2,  10,  21,  24,  16,   6,   1;
  2,  12,  31,  45,  40,  22,   7,   1;
  2,  14,  43,  76,  85,  62,  29,   8,   1;
  2,  16,  57, 119, 161, 147,  91,  37,   9,   1;
  ...

Cf. A129686, A007318, A124725.

Cf. Columns: A046698, A004277, A002061, A006527, A006007, A081282

A129686 * A007318 (Pascal's Triangle), as infinite lower triangular matrices.

T(n,k) = T(n-1,k) + T(n-1,k-1), T(0,0) = T(1,0) = T(1,1) = T(2,2) = 1, T(2,0) = T(2,1) = 2, T(n,k) = 0 if k<0 or if k>n. - Philippe Deléham, Feb 12 2014

More terms from Philippe Deléham, Feb 12 2014

A129765 Triangle, (1, 1, 2, 2, 2, ...) in every column.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 2, 2, 2, 1, 1, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1

Offset: 1

Gary W. Adamson, May 16 2007

Row sums = A004277, (1, 2, 4, 6, 8, 10, ...). Binomial transform of (1, 1, 2, 2, 2, ...) = A000325, starting (1, 2, 5, 12, 27, 58, ...). Binomial transform of A130196 = A130197, a triangle with row sums = the Cullen numbers, A002064.

			First few rows of the triangle:
  1;
  1, 1;
  2, 1, 1;
  2, 2, 1, 1;
  2, 2, 2, 1, 1;
  ...

Cf. A004277, A002064, A000325, A130197.

A129765 := proc(n,m) if abs(n-m)<2 then 1 ; else 2 ; end if ; end proc:
for n from 1 to 18 do for m from 1 to n do printf("%d,", A129765(n,m)) ; od ; od ; # R. J. Mathar, Jun 08 2007

Table[PadLeft[{1,1},n,2],{n,20}]//Flatten (* Harvey P. Dale, May 20 2019 *)

Triangle, (1, 1, 2, 2, 2, ...) in every column. By rows, (1; 1, 1; 2, 1, 1; ...), continuing with (n-2) 2's followed by two 1's. Inverse of A000012 as an infinite lower triangular matrix (all 1's and the rest zeros), signed by columns: (+ - - + + - -, ...).

More terms from R. J. Mathar, Jun 08 2007

A168441 Expansion of 1/(1-x/(1-2x/(1-4x/(1-6x/(1-8x/(1-.... (continued fraction).

Original entry on oeis.org

1, 1, 3, 17, 155, 2025, 34819, 743329, 18937707, 560071193, 18844479635, 710440531665, 29654234779771, 1357326276747721, 67589738142784803, 3637403230889380097, 210358430818676801675, 13009719599952748481145

Offset: 0

Paul Barry, Nov 25 2009

Hankel transform is A168442.

Cf. A004277, A111106, A168442.

nmax = 20; CoefficientList[1 + x*Series[1/(1 - x + ContinuedFractionK[-2*k*x, 1, {k, 1, nmax}]), {x, 0, nmax}], x] (* Vaclav Kotesovec, Jan 23 2024 *)

G.f.: 1/(1-x-2x^2/(1-6x-24x^2/(1-14x-80x^2/(1-22x-168x^2/(1-30x-288x^2/(1-... (continued fraction).
a(n) = Sum_{k=0..n} A111106(n,k)*2^(n-k). - Philippe Deléham, Nov 28 2009
a(n) = upper left term of M^n, M = an infinite square production matrix as follows:
  1, 1, 0, 0, 0, 0, ...
  2, 2, 2, 0, 0, 0, ...
  4, 4, 4, 4, 0, 0, ...
  6, 6, 6, 6, 6, 0, ...
  8, 8, 8, 8, 8, 8, ...
  ...
(where the series (1,2,4,6,8,...) = A004277, positive even integers prefaced with a 1). - Gary W. Adamson, Jul 19 2011
G.f. 1 + x/(G(0)-x) where G(k) = 1 - x*(2*k+2)/G(k+1); (continued fraction). - Sergei N. Gladkovskii, Oct 28 2012
a(n) ~ 2^(2*n - 3/2) * n^(n-1) / exp(n). - Vaclav Kotesovec, Jan 23 2024

A229488 Conjecturally, possible differences between prime(k)^2 and the previous prime for some k.

Original entry on oeis.org

1, 2, 6, 8, 12, 14, 18, 20, 24, 26, 30, 32, 38, 42, 44, 48, 50, 54, 56, 60, 62, 66, 68, 72, 74, 78, 80, 84, 86, 90, 92, 96, 98, 102, 104, 108, 110, 114, 116, 120, 122, 126, 128, 132, 134, 138, 140, 146, 150, 152, 156, 158, 162, 164, 168, 170, 174, 176, 180

Offset: 1

T. D. Noe, Oct 21 2013

nonn

Are there any missing terms? The first 10^7 primes were examined. All these differences occur for some k < 10^5. Note that the first differences of these terms is 1, 2, 4, or 6.
From R. J. Mathar, Oct 29 2013: (Start)
This sequence of possible differences d= prime(k)^2 -q looks similar to A047238; 1 is an exception associated with the single even prime, 1=2^2-3.
[Reason: Otherwise primes are odd, squared primes are also odd, so the differences are even and therefore in the class {0,2,4} mod 6.
Furthermore primes are of the form 3n+1 or 3n+2, squared primes are of the form 9n^2+6n+1 or 9n^2+12n+4, so squared primes are of the form ==1 (mod 3).
The difference prime(k)^2-q is therefore the difference between a number ==1 (mod 3) and a number == {1,2} (mod 3) and therefore a number == {0,2} mod 3. This is never of the form 6n+4 ( == 1 mod 3). So the differences are in the class {0,2} mod 6, demonstrating that this is essentially a subsequence of A047238.]
Furthermore, differences 36, 144, 324,... of the form (6n)^2, A016910, appear in A047238 but not here, because prime(k)^2 -q=(6n)^2 is equivalent to prime(k)^2-(6n)^2 =q =(prime(k)+6n)*(prime(k)-6n), which requires an explicit factorization of the prime q. This is a contradiction if we assure that prime(k)-6n is not equal 1; if we scanned explicitly all primes up to prime(k)=10^7, for example, all (6n)^2 up to 6n<=10^7 are proved not to be in the sequence. (End)

Cf. A000040 (primes), A001248 (primes squared).
Cf. A004277 (conjecturally, possible gaps between adjacent primes).
Cf. A054270 (prime below prime(n)^2).
Cf. A229489 (possible differences between prime(k)^2 and the next prime).

t = Table[p2 = Prime[k]^2; p2 - NextPrime[p2, -1], {k, 100000}]; Take[Union[t], 60]

A230486 Numbers n such that n^n is representable as the sum of two nonzero squares.

Original entry on oeis.org

5, 10, 13, 17, 20, 25, 26, 29, 30, 34, 37, 40, 41, 50, 52, 53, 58, 60, 61, 65, 68, 70, 73, 74, 78, 80, 82, 85, 89, 90, 97, 100, 101, 102, 104, 106, 109, 110, 113, 116, 120, 122, 125, 130, 136, 137, 140, 145, 146, 148, 149, 150, 156, 157, 160, 164, 169, 170

Offset: 1

Alex Ratushnyak, Oct 20 2013

nonn

If n is even, then n must have a prime factor of the form 4k+1. If n is odd, then all prime factors must be of the form 4k+1. - T. D. Noe, Oct 21 2013

The above is also a sufficient condition: the sequence consists exactly in even multiples of Pythagorean primes A002144, and products of such primes (A008846). - M. F. Hasler, Sep 02 2018

			5^5 = 55^2 + 10^2.
10^10 = 99712^2 + 7584^2.
13^13 = 17106843^2 + 3198598^2.
17^17 = 28735037644^2 + 1240110271^2.

G. H. Hardy and E. M. Wright, Theory of Numbers, Oxford, Sixth Edition, 2008, p. 395.

T. D. Noe, Table of n, a(n) for n = 1..1000

Cf. A000312 (n^n), A004431, A132777.
A subsequence of A000404 (numbers that are the sum of 2 nonzero squares).
Sequence A002144 (primes of the form 4k + 1) and A008846 (products of such primes) are subsequences.

t = {}; Do[f = FactorInteger[n]; p = Transpose[f][[1]]; If[EvenQ[n], If[MemberQ[Mod[p, 4], 1], AppendTo[t, n]], If[Union[Mod[p, 4]] == {1}, AppendTo[t, n]]], {n, 2, 200}]; t (* T. D. Noe, Oct 21 2013 *)

select( is_A230486(n)={(n=factor(n)[,1]%4) && if(n[1]==2, Set(n)[1]==1, Set(n)==[1])}, [1..200]) \\ M. F. Hasler, Sep 02 2018

from itertools import count, islice
from sympy import primefactors
def A230486_gen(startvalue=2): # generator of terms >= startvalue
    return filter(lambda n:all(p&3==1 for p in primefactors(n)) if n&1 else any(p&3==1 for p in primefactors(n)),count(max(startvalue,2)))
A230486_list = list(islice(A230486_gen(),20)) # Chai Wah Wu, May 15 2023

A230486 = { n | A000312(n) is in A000404 } = A004277*A002144 U A008846. - M. F. Hasler, Sep 02 2018

Extended by T. D. Noe, Oct 21 2013

A058034 Number of numbers whose cube root rounds to n.

Original entry on oeis.org

1, 3, 12, 27, 49, 75, 108, 147, 193, 243, 300, 363, 433, 507, 588, 675, 769, 867, 972, 1083, 1201, 1323, 1452, 1587, 1729, 1875, 2028, 2187, 2353, 2523, 2700, 2883, 3073, 3267, 3468, 3675, 3889, 4107, 4332, 4563, 4801, 5043, 5292, 5547, 5809, 6075, 6348

Offset: 0

Henry Bottomley, Nov 22 2000

			a(2)=12 since the cube roots of 4, 5, 6, ..., 15 all lie between 1.5 and 2.5.

Robert Israel, Table of n, a(n) for n = 0..10000
Index entries for linear recurrences with constant coefficients, signature (2,-1,0,1,-2,1).

Cf. A003215 for number whose floor (or ceiling) of the cube root is n, A004277 for number whose square root rounds to n.

[n mod 4 eq 0 select 3*n^2+1 else 3*n^2: n in [0..80]]; // Vincenzo Librandi, Dec 25 2015

seq(1 + floor((n+1/2)^3) - ceil((n-1/2)^3), n = 0 .. 100);

Table[SeriesCoefficient[-(3 x^5 + 6 x^4 + 6 x^3 + 7 x^2 + x + 1)/((x - 1)^3 (x + 1) (x^2 + 1)), {x, 0, n}], {n, 0, 46}] (* Michael De Vlieger, Dec 24 2015 *)
LinearRecurrence[{2, -1, 0, 1, -2, 1}, {1, 3, 12, 27, 49, 75}, 50] (* Vincenzo Librandi, Dec 25 2015 *)

Vec(-(3*x^5+6*x^4+6*x^3+7*x^2+x+1)/((x-1)^3*(x+1)*(x^2+1)) + O(x^100)) \\ Colin Barker, Jul 04 2014

a(n) = 3n^2+1 if n == 0 (mod 4), 3n^2 otherwise.
a(n) = A033428(n)+A011765(n) = A034131(n-1)-A034131(n-2).
a(n) = (1+(-1)^n+(-i)^n+i^n+12*n^2)/4 where i=sqrt(-1). - Colin Barker, Jul 04 2014
G.f.: -(3*x^5+6*x^4+6*x^3+7*x^2+x+1) / ((x-1)^3*(x+1)*(x^2+1)). - Colin Barker, Jul 04 2014

cp's OEIS Frontend

A356148 a(n) is the number of positive integers whose binary expansion appears as a substring in the binary expansion of n or its complement.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Python

Formula

A084859 Binomial transform of Cullen numbers A002064.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A086460 Square array read by antidiagonals: T(n,k)=nk+0^n.

Views

Author

Keywords

Comments

Examples

Formula

A113322 First differences of A113321.

Views

Author

Keywords

Comments

A129687 A129686 * A007318.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A129765 Triangle, (1, 1, 2, 2, 2, ...) in every column.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A168441 Expansion of 1/(1-x/(1-2x/(1-4x/(1-6x/(1-8x/(1-.... (continued fraction).

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

A229488 Conjecturally, possible differences between prime(k)^2 and the previous prime for some k.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

A230486 Numbers n such that n^n is representable as the sum of two nonzero squares.

Views

Author

Keywords

Comments

Examples

References

Links