A175046 -id:A175046 - cp's OEIS frontend

A319423 Indices of records in A175046.

1, 2, 4, 5, 9, 10, 18, 20, 21, 37, 41, 42, 74, 82, 84, 85, 149, 165, 169, 170, 298, 330, 338, 340, 341, 597, 661, 677, 681, 682, 1194, 1322, 1354, 1362, 1364, 1365, 2389, 2645, 2709, 2725, 2729, 2730, 4778, 5290, 5418, 5450, 5458, 5460, 5461, 9557

Offset: 1

N. J. A. Sloane, Sep 23 2018

nonn

a(n) in binary is either an alternating string of 1's and 0's, or exactly one of the 0's is replaced by 00 (see paper in links). - Chai Wah Wu, Oct 04 2018

Chai Wah Wu, Table of n, a(n) for n = 1..10099
Chai Wah Wu, Record values in appending and prepending bitstrings to runs of binary digits, arXiv:1810.02293 [math.NT], 2018

Cf. A086638, A175046, A319422, A319424.

A319422 Records in A175046.

Original entry on oeis.org

3, 12, 24, 51, 99, 204, 396, 408, 819, 1587, 1635, 3276, 6348, 6540, 6552, 13107, 25395, 26163, 26211, 52428, 101580, 104652, 104844, 104856, 209715, 406323, 418611, 419379, 419427, 838860, 1625292, 1674444, 1677516, 1677708, 1677720, 3355443, 6501171

Offset: 1

N. J. A. Sloane, Sep 23 2018

nonn

a(n) in binary is either an alternating string of 11's and 00's, or exactly one of the 00's is replaced by 000 (see A319423). - Chai Wah Wu, Oct 04 2018

Chai Wah Wu, Table of n, a(n) for n = 1..10099
Chai Wah Wu, Record values in appending and prepending bitstrings to runs of binary digits, arXiv:1810.02293 [math.NT], 2018

Cf. A175046, A319423, A319424 (written in binary).

b[n_] := (Append[#, #[[1]]]& /@ Split[IntegerDigits[n, 2]]) // Flatten // FromDigits[#, 2]&;
Reap[For[rec = 0; k = 1, k < 3000, k++, bk = b[k]; If[bk > rec, rec = bk; Sow[rec]]]][[2, 1]] (* Jean-François Alcover, Nov 12 2018 *)

A319424 Records in A175046 (but written in base 2).

Original entry on oeis.org

11, 1100, 11000, 110011, 1100011, 11001100, 110001100, 110011000, 1100110011, 11000110011, 11001100011, 110011001100, 1100011001100, 1100110001100, 1100110011000, 11001100110011, 110001100110011, 110011000110011, 110011001100011, 1100110011001100, 11000110011001100, 11001100011001100, 11001100110001100, 11001100110011000, 110011001100110011, 1100011001100110011

Offset: 1

N. J. A. Sloane, Sep 23 2018

More terms than usual are given in order to display the pattern.
Conjecture. a(n) is either an alternating string of 11's and 00's, or exactly one of the 00's is replaced by 000.
Conjecture is true (see A319423). - Chai Wah Wu, Oct 04 2018

Chai Wah Wu, Table of n, a(n) for n = 1..10099
N. J. A. Sloane, Transforms
Chai Wah Wu, Record values in appending and prepending bitstrings to runs of binary digits, arXiv:1810.02293 [math.NT], 2018

Cf. A175406, A319422, A319423.

A319407 a(n) = A175046(n)-n.

Original entry on oeis.org

2, 10, 4, 20, 46, 22, 8, 40, 90, 194, 92, 44, 102, 46, 16, 80, 178, 378, 180, 388, 798, 390, 184, 88, 202, 434, 204, 92, 214, 94, 32, 160, 354, 746, 356, 756, 1550, 758, 360, 776, 1594, 3234, 1596, 780, 1606, 782, 368, 176, 402, 858, 404, 868, 1790, 870

Offset: 1

N. J. A. Sloane, Sep 19 2018

How much n increases by when its binary runs are all prolonged by one bit.

			n = 13 = 1101_2 -> 1110011_2 = 115 so a(13) = 115 - 13 = 102.

Altug Alkan, Table of n, a(n) for n = 1..16384

Cf. A175046, A319408, A319409.

A318925 a(n) = A175046(A318921(n)).

Original entry on oeis.org

0, 0, 0, 3, 0, 0, 3, 7, 0, 0, 0, 3, 12, 3, 7, 15, 0, 0, 0, 3, 0, 0, 3, 7, 24, 12, 3, 7, 28, 7, 15, 31, 0, 0, 0, 3, 0, 0, 3, 7, 0, 0, 0, 3, 12, 3, 7, 15, 48, 24, 12, 51, 12, 3, 7, 15, 56, 28, 7, 15, 60, 15, 31, 63, 0, 0, 0, 3, 0, 0, 3, 7, 0, 0, 0, 3, 12, 3, 7

Offset: 0

N. J. A. Sloane, Sep 09 2018

Inspired by Andrew Weimholt's observation that A318921(A175046(n)) = A001477(n).
As in A318921, the empty string is represented by 0.
a(n) = n iff every run in the binary expansion of n has length at least 2, and otherwise a(n) < n.

Rémy Sigrist, Table of n, a(n) for n = 0..16384

Cf. A318921, A175046, A001477.

More terms from Rémy Sigrist, Sep 09 2018

A324127 Partial sums of A175046.

Original entry on oeis.org

3, 15, 22, 46, 97, 125, 140, 188, 287, 491, 594, 650, 765, 825, 856, 952, 1147, 1543, 1742, 2150, 2969, 3381, 3588, 3700, 3927, 4387, 4618, 4738, 4981, 5105, 5168, 5360, 5747, 6527, 6918, 7710, 9297, 10093, 10492, 11308, 12943, 16219, 17858, 18682

Offset: 1

N. J. A. Sloane, Feb 19 2019

For the average value, see the Nov 18 2018 comment from Chai Wah Wu in A175046.

Cf. A175046.

A008966 a(n) = 1 if n is squarefree, otherwise 0.

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane

a(n) depends only on prime signature of n (cf. A025487). So a(24) = a(375) since 24 = 2^3*3 and 375 = 3*5^3 both have prime signature (3, 1).

The infinite lower triangular matrix with A008966 on the main diagonal and the rest zeros is the square of triangle A143255. - Gary W. Adamson, Aug 02 2008

Daniel Forgues, Table of n, a(n) for n = 1..100000
Eric Weisstein's World of Mathematics, Moebius Function
Index entries for characteristic functions
Index entries for sequences computed from exponents in factorization of n

Cf. A005117, A008836 (Dirichlet inverse), A013928 (partial sums).
Cf. A179211, A179212, A179213, A179214, A179215.
Cf. A020639, A073576, A087188.
Cf. A124010, A212793, A085357, A156552.
Parity of A002033.
Cf. A047999, A036987
Cf. A082020 (Dgf at s=2), A157289 (Dgf at s=3), A157290 (Dgf at s=4).

a008966 = abs . a008683
-- Reinhard Zumkeller, Dec 13 2015, Dec 15 2014, May 27 2012, Jan 25 2012

Magma
```
[ Abs(MoebiusMu(n)) : n in [1..100]];
```

A008966 := proc(n) if numtheory[issqrfree](n) then 1 ; else 0 ; end if; end proc: # R. J. Mathar, Mar 14 2011

A008966[n_] := Abs[MoebiusMu[n]]; Table[A008966[n], {n, 100}] (* Enrique Pérez Herrero, Apr 15 2010 *)
Table[If[SquareFreeQ[n],1,0],{n,100}] (* or *) Boole[SquareFreeQ/@ Range[ 100]] (* Harvey P. Dale, Feb 28 2015 *)

MuPAD
```
func(abs(numlib::moebius(n)), n):
```
PARI
```
a(n)=if(n<1,0,direuler(p=2,n,1+X))[n]
```

a(n)=issquarefree(n) \\ Michel Marcus, Feb 22 2015

from sympy import factorint
def A008966(n): return int(max(factorint(n).values(),default=1)==1) # Chai Wah Wu, Apr 05 2023

Dirichlet g.f.: zeta(s)/zeta(2s).
a(n) = abs(mu(n)), where mu is the Moebius function (A008683).
a(n) = 0^(bigomega(n) - omega(n)), where bigomega(n) and omega(n) are the numbers of prime factors of n with and without repetition (A001222, A001221, A046660). - Reinhard Zumkeller, Apr 05 2003
Multiplicative with p^e -> 0^(e - 1), p prime and e > 0. - Reinhard Zumkeller, Jul 15 2003
a(n) = 0^(A046951(n) - 1). - Reinhard Zumkeller, May 20 2007
a(n) = 1 - A107078(n). - Reinhard Zumkeller, Oct 03 2008
a(n) = floor(rad(n)/n), where rad() is A007947. - Enrique Pérez Herrero, Nov 13 2009
A175046(n) = a(n)*A073311(n). - Reinhard Zumkeller, Apr 05 2010
a(n) = floor(A000005(n^2)/A007425(n)). - Enrique Pérez Herrero, Apr 15 2010
a(A005117(n)) = 1; a(A013929(n)) = 0; a(n) = A013928(n + 1) - A013928(n). - Reinhard Zumkeller, Jul 05 2010
a(n) * A112526(n) = A063524(n). - Reinhard Zumkeller, Sep 16 2011
a(n) = mu(n) * lambda(n) = A008836(n) * A008683(n). - Enrique Pérez Herrero, Nov 29 2013
a(n) = Sum_{d|n} 2^omega(d)*mu(n/d). - Geoffrey Critzer, Feb 22 2015
a(n) = A085357(A156552(n)). - Antti Karttunen, Mar 06 2017
Limit_{n->oo} (1/n)*Sum_{j=1..n} a(j) = 6/Pi^2. - Andres Cicuttin, Aug 13 2017
a(1) = 1; a(n) = -Sum_{d|n, d < n} (-1)^bigomega(n/d) * a(d). - Ilya Gutkovskiy, Mar 10 2021

Deleted an unclear comment. - N. J. A. Sloane, May 30 2021

A318921 In binary expansion of n, delete one symbol from each run. Set a(n)=0 if the result is the empty string.

Original entry on oeis.org

0, 0, 0, 1, 0, 0, 1, 3, 0, 0, 0, 1, 2, 1, 3, 7, 0, 0, 0, 1, 0, 0, 1, 3, 4, 2, 1, 3, 6, 3, 7, 15, 0, 0, 0, 1, 0, 0, 1, 3, 0, 0, 0, 1, 2, 1, 3, 7, 8, 4, 2, 5, 2, 1, 3, 7, 12, 6, 3, 7, 14, 7, 15, 31, 0, 0, 0, 1, 0, 0, 1, 3, 0, 0, 0, 1, 2, 1, 3, 7, 0, 0, 0, 1, 0, 0, 1, 3, 4, 2, 1, 3, 6, 3, 7, 15, 16

Offset: 0

N. J. A. Sloane, Sep 08 2018

If the binary expansion of n is 1^b 0^c 1^d 0^e ..., then a(n) is the number whose binary expansion is 1^(b-1) 0^(c-1) 1^(d-1) 0^(e-1) .... Leading 0's are omitted, and if the result is the empty string, here we set a(n) = 0. See A319419 for a version which represents the empty string by -1.
Lenormand refers to this operation as planing ("raboter") the runs (or blocks) of the binary expansion.
A175046 expands the runs in a similar way, and a(A175046(n)) = A001477(n). - Andrew Weimholt, Sep 08 2018. In other words, this is a left inverse to A175046: A318921 o A175046 = A001477 = id on [0..oo). - M. F. Hasler, Sep 10 2018
Conjecture: For n in the range 2^k, ..., 2^(k+1)-1, the total value of a(n) appears to be 2*3^(k-1) - 2^(k-1) (see A027649), and so the average value of a(n) appears to be (3/2)^(k-1) - 1/2. - N. J. A. Sloane, Sep 25 2018
The above conjecture was proved by Doron Zeilberger on Nov 16 2018 (see link) and independently by Chai Wah Wu on Nov 18 2018 (see below). - N. J. A. Sloane, Nov 20 2018
From Chai Wah Wu, Nov 18 2018: (Start)
Conjecture is correct for k > 0. Proof: looking at the least significant 2 bits of n, it is easy to see that a(4n) = 2a(2n), a(4n+1) = a(2n), a(4n+2) = a(2n+1) and a(4n+3) = 2a(2n+1)+1. Define f(k) = Sum_{i=2^k..2^(k+1)-1} a(i), i.e. the sum ranges over all numbers with a (k+1)-bit binary expansion. Thus f(0) = a(1) = 0 and f(1) = a(2)+a(3) = 1. By summing over the recurrence relations for a(n), we get f(k+2) = Sum_{i=2^k..2^(k+1)-1} (f(4i) + f(4i+1) + f(4i+2) + f(4i+3)) = Sum_{i=2^k..2^(k+1)-1} (3a(2i) + 3a(2i+1) + 1) = 3*f(k+1) + 2^k. Solving this first order recurrence relation with the initial condition f(1) = 1 shows that f(k) = 2*3^(k-1)-2^(k-1) for k > 0.
(End)

			      n / "planed" string / a(n)
      0   e 0 (e = empty string)
      1   e 0
     10   e 0
     11   1 1
    100   0 0
    101   e 0
    110   1 1
    111  11 3
   1000  00 0
   1001   0 0
   1010   e 0
   1011   1 1
   1100  10 2
   1101   1 1
   1110  11 3
   1111 111 7
  10000 000 0
  ...

N. J. A. Sloane, Table of n, a(n) for n = 0..16384
Yonah Biers-Ariel, A Generalization of the 'Raboter' Operation, arXiv:1902.06354 [math.CO], 2019.
Claude Lenormand, Deux transformations sur les mots, Preprint, 5 pages, Nov 17 2003. Apparently unpublished. This is a scanned copy of the version that the author sent to me in 2003.
N. J. A. Sloane, Coordination Sequences, Planing Numbers, and Other Recent Sequences (II), Experimental Mathematics Seminar, Rutgers University, Jan 31 2019, Part I, Part 2, Slides. (Mentions this sequence)
Chai Wah Wu, Record values in appending and prepending bitstrings to runs of binary digits, arXiv:1810.02293 [math.NT], 2018.
Doron Zeilberger, Proof of a Conjecture of Neil Sloane Concerning Claude Lenormand's ``Raboter" Operation (OEIS sequence A318921), Nov 16 2018; Local copy, pdf file only, no active links

Cf. A027649 (average value), A175046, A319419 (a version where a(n)=-1 if the result is the empty string).

A073311 Number of squarefree numbers in the reduced residue system of n.

Original entry on oeis.org

1, 1, 2, 2, 3, 2, 5, 4, 4, 3, 7, 4, 8, 5, 6, 7, 11, 6, 12, 7, 8, 9, 15, 8, 13, 10, 13, 9, 17, 8, 19, 13, 13, 13, 15, 11, 23, 15, 17, 14, 26, 11, 28, 17, 18, 18, 30, 15, 26, 17, 21, 19, 32, 16, 25, 20, 23, 23, 36, 15, 37, 25, 26, 26, 30, 18, 41, 26, 29, 22, 44, 22, 45, 30, 29, 29, 36

Offset: 1

Reinhard Zumkeller, Jul 25 2002

nonn

Number of positive squarefree numbers <= n that are relatively prime to n.

			n=15, there are A000010(15)=8 residues: 1, 2, 4=2^2, 7, 8=2^3, 11, 13 and 14; six of them are squarefree: 1, 2, 7, 11, 13 and 14, therefore a(15)=6. [Typo fixed by _Reinhard Zumkeller_, Mar 19 2010]

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Steven R. Finch, Unitarism and infinitarism.
Steven R. Finch, Unitarism and Infinitarism, February 25, 2004. [Cached copy, with permission of the author]
Steven R. Finch, Mathematical Constants II, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018, p. 49-50.

Cf. A073312, A005117, A000010, A048864, A048865, A065463.

a073311 = sum . map a008966 . a038566_row
-- Reinhard Zumkeller, Jul 04 2012

[&+[MoebiusMu(&*PrimeDivisors(k)*i)^2:i in [1..k]]: k in [1..65]]; // Marius A. Burtea, Jul 27 2019

with(numtheory): rad := n -> mul(p, p in factorset(n)):
seq(add(mobius(rad(n)*i)^2, i=1..n), n=1..100); # Ridouane Oudra, Jul 27 2019

a[n_] := Select[Range[n], SquareFreeQ[#] && CoprimeQ[#, n]&] // Length;
Array[a, 100] (* Jean-François Alcover, Dec 12 2021 *)

a(n)=my(s=1); forfactored(k=2,n-1, if(vecmax(k[2][,2])==1 && gcd(k[1],n)==1, s++)); s \\ Charles R Greathouse IV, Nov 05 2017

a(n) + A073312(n) = A000010(n).
Let s(n) = Sum_{k=1..n} a(k). Then s(n) is asymptotic to C*n^2 where C = (3/Pi^2)*alpha and alpha = Product_{p prime} (1 - 1/(p*(p+1))) = A065463 = 0.7044422009... [From discussions in Number Theory List, Apr 06 2004]
A175046(n) = a(n)*A008966(n). - Reinhard Zumkeller, Apr 05 2010
a(n) = Sum_{k=1..A000010(n)} A008966(A038566(n,k)). - Reinhard Zumkeller, Jul 04 2012
a(n) = Sum_{i=1..n} mu(A007947(n)*i)^2, where mu is the Moebius function (A008683). - Ridouane Oudra, Jul 27 2019
a(n) = Sum_{1<=k<=n, gcd(n,k)=1} mu(k)^2. - Ridouane Oudra, May 25 2023

A175047 Write n in binary, then increase each run of 0's by one 0. a(n) is the decimal equivalent of the result.

Original entry on oeis.org

1, 4, 3, 8, 9, 12, 7, 16, 17, 36, 19, 24, 25, 28, 15, 32, 33, 68, 35, 72, 73, 76, 39, 48, 49, 100, 51, 56, 57, 60, 31, 64, 65, 132, 67, 136, 137, 140, 71, 144, 145, 292, 147, 152, 153, 156, 79, 96, 97, 196, 99, 200, 201, 204, 103, 112, 113, 228, 115, 120, 121, 124, 63, 128

Offset: 1

Leroy Quet, Dec 02 2009

From Reinhard Zumkeller, Dec 12 2009: (Start)
A070939(a(n)) = A070939(n) + A033264(n);
A171598 and A171599 give record values and where they occur. (End)

			12 in binary is 1100. Increase each run of 0 by one digit to get 11000, which is 24 in decimal. So a(12) = 24.

R. Zumkeller, Table of n, a(n) for n = 1..10000

Cf. A175046, A175048.
Cf. A084471. - Robert G. Wilson v, Dec 11 2009
Cf. A030308, A106151, A007088.

import Data.List (group)
a175047 = foldr (\b v -> 2 * v + b) 0 . concatMap
   (\bs@(b:_) -> if b == 0 then 0 : bs else bs) . group . a030308_row
-- Reinhard Zumkeller, Jul 05 2013

f[n_] := Block[{s = Split@ IntegerDigits[n, 2]}, FromDigits[ Flatten@ Insert[s, {0}, Table[{2 i}, {i, Floor[ Length@s/2]} ]], 2]]; Array[ f, 64] (* Robert G. Wilson v, Dec 11 2009 *)

from re import split
def A175047(n):
  return int(''.join(d+'0' if '0' in d else d for d in split('(0+)|(1+)',bin(n)[2:]) if d != '' and d != None),2) # Chai Wah Wu, Nov 21 2018

a(n) = if n<2 then n else 2*(1 + 0^((n+2) mod 4))*a([n/2]) + n mod 2. - Reinhard Zumkeller, Jan 20 2010

a(2^n) = 2^(n+1). - Chai Wah Wu, Nov 21 2018

Extended by Ray Chandler, Dec 18 2009

a(11) onwards from Robert G. Wilson v and Reinhard Zumkeller, Dec 11 2009

cp's OEIS Frontend

A319423 Indices of records in A175046.

Views

Author

Keywords

Comments

Links

Crossrefs

A319422 Records in A175046.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A319424 Records in A175046 (but written in base 2).

Views

Author

Keywords

Comments

Links

Crossrefs

A319407 a(n) = A175046(n)-n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A318925 a(n) = A175046(A318921(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A324127 Partial sums of A175046.

Views

Author

Keywords

Comments

Crossrefs

A008966 a(n) = 1 if n is squarefree, otherwise 0.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

MuPAD

PARI

PARI

Python

Formula

Extensions

A318921 In binary expansion of n, delete one symbol from each run. Set a(n)=0 if the result is the empty string.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

Python

Formula