I generally don't like "base" sequences, but when OEIS indulges in them (which it always, always does), we ought to include the B=2 case. So I present for your delectation, the binary analogue of a018851: 0,1,2,5,2,9,5,11 ... On Sun, May 22, 2016 at 9:34 AM, David Wilson <davidwwilson@comcast.net> wrote:

The last paragraph should read

r(n) <= 2*sqrt(10)*n is a tight upper bound. It is approached by numbers slightly larger than 25*10^j for large j. For example r(250044723) = 1581280251.

-----Original Message----- From: math-fun [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of David Wilson Sent: Sunday, May 22, 2016 9:28 AM To: 'math-fun' Subject: Re: [math-fun] squares beginning with n

Let r(n) be the smallest value for which r(n)^2 starts with n.

Let n >= 1. Let k(n) = floor(log10(n)) + 2 = (number of digits in n) + 1.

Then, if m(n) = ceil(sqrt(n * 10^k(n))), m(n)^2 starts with n. If r(n) >= 1 is the smallest positive integer with such that r(n)^2 starts with n, then r(n) = ceil(sqrt(n * 10^k)) for some k <= k(n).

r(n)^2 <= 40*n is a tight bound. This bound is approached by numbers slightly larger than 25*10^j, for example

...

-----Original Message----- From: math-fun [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of Neil Sloane Sent: Saturday, May 21, 2016 8:45 PM To: fun Subject: [math-fun] squares beginning with n

Given n, A018851 and A018796 give the smallest square that begins with n

Question: does such a square always exist, and if so how big can the smallest example be? _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

99% of OEIS is "base-10 stuff". Zak

Воскресенье, 22 мая 2016, 18:11 +03:00 от Dan Asimov <dasimov@earthlink.net>:

I'm the same way. Especially base-10 stuff puts me to sleep immediately, like drinking a cup of decaf coffee.

—Dan

...

On May 22, 2016, at 6:50 AM, Allan Wechsler < acwacw@gmail.com > wrote:

I generally don't like "base" sequences, but ...

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

On 2016-05-22 09:03, Veit Elser wrote:

Really? I would have thought base-10 has a special place in your heart. After all, in what base is the entropy per digit closest to the entropy per term in the continued fraction expansion?

-Veit

Eleven! In[709]:= π^2/6/Log[2]/Log[{10, 11}] Out[709]= {π^2/(6 Log[2] Log[10]), π^2/(6 Log[2] Log[11])} In[710]:= N@% Out[710]= {1.030640834100713, 0.9896755074135375} Sagan's "Contact" was onto something?

...

On May 22, 2016, at 11:11 AM, Dan Asimov <dasimov@earthlink.net> wrote:

I'm the same way.

Amen. Especially base-10 stuff puts me to sleep immediately,

...

like drinking a cup of decaf coffee.

—Dan

___________

Re SETI sequences: What if SETI has already been receiving prime sequences, but the aliens didn't want to bore us with the stuff early on in these sequences? Or the aliens started broadcasting the sequences when they first received radio transmissions from Earth, but we hadn't yet started listening ? Would we be able to recognize these sequences in any way ? At 01:01 PM 5/22/2016, rwg wrote:

Sagan's "Contact" was onto something?

Base 10 is useful for mentally splitting a small number into two squares. After removing factors of 2 and 5, the remaining cofactor of the target will end in digit 1,3,7,or9. For 1 and 9, the split must either be xxx00 + y^2, or xxe25 + y^2. (e is an even digit.) For 3 and 7, double the target to end in 6 or 4; the split must be xxe25 + y^2. example: 2089 = a^2 + b^2, find all splits. If the split is xxx00+y^2, y^2 must end in 89. y must end in 17,33,67,or 89. 17 and 33 are in range. trying these, a^2 is 1800 or 1000. no joy. If the split is xxe25+y^2, y^2 must end in e64. Y must end in 8 or 92. (42 & 58 squared end in o64.) 8 is in range. 2089-64 = 2025, bingo. the only split. since gcd(8,45) is 1, 2089 is prime. example: 1997: split 3994 into xxe25 + xxo69. y must end in 13,37,63,or 87. 87 is too big; the others give 3994-y^2 = 3825, 2625, 25. 3825 is excluded because the hundreds digit must be 0,2,or 6; 8 is not. 2625 is excluded because 26 is not of the form n^2 + n. (The bracketing squares for 26 are 25 and 36, and n2+n is near the middle.) 3994-63^2 = 25 scores. since 63 and 5 are relatively prime, 1997 is prime. The split is average & semidifference of 5,63: 34, 29; 1156+841. Base ten is especially useful for this exercise, because 5 is a very small 4k+1 prime, and using an even base simplifies determining the residue of a number mod 4 or 8. (Odd squares must be 8k+1, explaining the e in e25.) Determining whether a number is odd or even, in an odd base, requires examining every digit. --- re spigot: the spigot algorithm for e is "represent in factorial base, convert to decimal by repeatedly multiplying by 10 and printing the integer digit (and discarding it)". This works for any conventional base. Gosper's continued fraction arithmetic allows base conversion, and can be done as a spigot algorithm in a natural way. 10 is not special. re BBP (not spigot): I don't know of anything for pi except base = powers of 2. For natural logs, You can fiddle around with logs of 1 + delta, where delta is "nice" in your chosen base. For base 3, this gets log of 2/3, 4/3, 10/9, 26/27, ... Some adds & subtracts will get you log of 2, 3, 5, 7, 11, 13, and some sporadic larger primes in ternary. Base 2 is even better, but I can't see how to separate out log23 from 2047 = 23*89. In base 10, you can get log of 9/10, 11/10, ..., of limited interest. I think the BBP pi formula can be interpreted as a linear combination of logs with (small) complex deltas, but Mr. P is better qualified to enlighten us on this point. Rich --------------- Quoting Mike Stay <metaweta@gmail.com>:

Is there anything interesting at all number-theoretically about base 10? Binary is obviously special for a lot of reasons. Ternary has the smallest radix economy, being closest to e, but that's all I can think of off the top of my head for why it would be better than some other base. Poking through my list archive, Gosper's 2005 email "squarefree string draws Sierpinski triangle" talks about some interesting stuff you can do with the alternating sum of nonzero digits in balanced ternary. The BBP algorithm for pi uses base 16, but I don't understand why well enough to know if that's fundamental or whether there are spigot algorithms for pi in any base. There are probably special things about a base being prime. But is there anything interesting about base 10?

Also, in our native, base - 10,  numbers divisible by 3 has sum of digits also divisible by 3, while base - 2 has nothing similar.

Вторник, 24 мая 2016, 19:17 +03:00 от Mike Stay <metaweta@gmail.com>:

Thanks, Rich!

On Mon, May 23, 2016 at 8:45 PM, < rcs@xmission.com > wrote:

...

Base 10 is useful for mentally splitting a small number into two squares.

After removing factors of 2 and 5, the remaining cofactor of the target will end in digit 1,3,7,or9. For 1 and 9, the split must either be xxx00 + y^2, or xxe25 + y^2. (e is an even digit.) For 3 and 7, double the target to end in 6 or 4; the split must be xxe25 + y^2.

example: 2089 = a^2 + b^2, find all splits. If the split is xxx00+y^2, y^2 must end in 89. y must end in 17,33,67,or 89. 17 and 33 are in range. trying these, a^2 is 1800 or 1000. no joy. If the split is xxe25+y^2, y^2 must end in e64. Y must end in 8 or 92. (42 & 58 squared end in o64.) 8 is in range. 2089-64 = 2025, bingo. the only split. since gcd(8,45) is 1, 2089 is prime.

example: 1997: split 3994 into xxe25 + xxo69. y must end in 13,37,63,or 87. 87 is too big; the others give 3994-y^2 = 3825, 2625, 25. 3825 is excluded because the hundreds digit must be 0,2,or 6; 8 is not. 2625 is excluded because 26 is not of the form n^2 + n. (The bracketing squares for 26 are 25 and 36, and n2+n is near the middle.) 3994-63^2 = 25 scores. since 63 and 5 are relatively prime, 1997 is prime. The split is average & semidifference of 5,63: 34, 29; 1156+841.

Base ten is especially useful for this exercise, because 5 is a very small 4k+1 prime, and using an even base simplifies determining the residue of a number mod 4 or 8. (Odd squares must be 8k+1, explaining the e in e25.) Determining whether a number is odd or even, in an odd base, requires examining every digit.

---

re spigot: the spigot algorithm for e is "represent in factorial base, convert to decimal by repeatedly multiplying by 10 and printing the integer digit (and discarding it)". This works for any conventional base. Gosper's continued fraction arithmetic allows base conversion, and can be done as a spigot algorithm in a natural way. 10 is not special.

re BBP (not spigot):

I don't know of anything for pi except base = powers of 2.

For natural logs, You can fiddle around with logs of 1 + delta, where delta is "nice" in your chosen base. For base 3, this gets log of 2/3, 4/3, 10/9, 26/27, ... Some adds & subtracts will get you log of 2, 3, 5, 7, 11, 13, and some sporadic larger primes in ternary. Base 2 is even better, but I can't see how to separate out log23 from 2047 = 23*89. In base 10, you can get log of 9/10, 11/10, ..., of limited interest.

I think the BBP pi formula can be interpreted as a linear combination of logs with (small) complex deltas, but Mr. P is better qualified to enlighten us on this point.

Rich

--------------- Quoting Mike Stay < metaweta@gmail.com >:

...

Is there anything interesting at all number-theoretically about base 10? Binary is obviously special for a lot of reasons. Ternary has the smallest radix economy, being closest to e, but that's all I can think of off the top of my head for why it would be better than some other base. Poking through my list archive, Gosper's 2005 email "squarefree string draws Sierpinski triangle" talks about some interesting stuff you can do with the alternating sum of nonzero digits in balanced ternary. The BBP algorithm for pi uses base 16, but I don't understand why well enough to know if that's fundamental or whether there are spigot algorithms for pi in any base. There are probably special things about a base being prime. But is there anything interesting about base 10?

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

The "11's" trick should work fine in base 2 for detecting multiples of 3. Count the number of 1's in even positions and the numbers of 1's in odd positions; iff these differ by a multiple of 3, you have a multiple of 3. On Tue, May 24, 2016 at 10:52 AM, Dan Asimov <dasimov@earthlink.net> wrote:

Zak, good question: Is there a quick way to detect multiples of 3 expressed in base 2 ??? Let's see:

(2 + 1) (2^a + 2^b + ... + 2^c) =

2^(a+1) + 2^a + 2^(b+1) + 2^b + ... + 2^(c+1) + 2^c.

Hmm, if all these exponents are distinct, this pattern seems very easy to detect.

But what if some of the exponents are equal?

I bet there's a simple algorithm to untangle them.

But I may be wrong.

—Dan

...

On May 24, 2016, at 9:56 AM, Zak Seidov via math-fun < math-fun@mailman.xmission.com> wrote:

Also, in our native, base - 10, numbers divisible by 3 has sum of digits also divisible by 3, while base - 2 has nothing similar.

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] --

Or you can do it as a rewriting system: 00 -> e 11 -> e 1010 -> 01 0101 -> 10 In prose, strike out identical pairs, and strike out the two digits on the end of abab patterns; repeat until you end with e (a multiple of 3) or 1 or 10 (not a power of 3). On Tue, May 24, 2016 at 11:04 AM, Victor Miller <victorsmiller@gmail.com> wrote:

Dan, Sure. Use the fact that 2^2 = 1 mod 3, so you "cast out 3's" -- take pairs of digits in binary, and add them up, and repeat the process as long as you have more than 2 bits.

For example 27 = 11011, so 11011 --> 1 + 10 + 11 = 110 --> 1 + 10 = 11, which is 3.

Victor

On Tue, May 24, 2016 at 1:52 PM, Dan Asimov <dasimov@earthlink.net> wrote:

...

Zak, good question: Is there a quick way to detect multiples of 3 expressed in base 2 ??? Let's see:

(2 + 1) (2^a + 2^b + ... + 2^c) =

2^(a+1) + 2^a + 2^(b+1) + 2^b + ... + 2^(c+1) + 2^c.

Hmm, if all these exponents are distinct, this pattern seems very easy to detect.

But what if some of the exponents are equal?

I bet there's a simple algorithm to untangle them.

But I may be wrong.

—Dan

...

On May 24, 2016, at 9:56 AM, Zak Seidov via math-fun < math-fun@mailman.xmission.com> wrote:

Also, in our native, base - 10, numbers divisible by 3 has sum of digits also divisible by 3, while base - 2 has nothing similar.

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] --

* Victor Miller <victorsmiller@gmail.com> [May 25. 2016 10:33]:

The language of numbers in base b which leave a set of remainders modulo d is a regular language, so you can recognize it via a finite automaton.

Victor [...]

For every base b and every (tentative) divisor d one can obtain a periodic sequence of weights such that the weighted sum of digits tells whether a base-b number is divisible by d. IIRC the sequence of weights corresponds to the sequence b^n mod d. I once wrote that up (on paper) but that is certainly lost. My warmup exercise was to find for base b the rules for d = b - 1 and d = b + 1. Cannot recall the details from the top of my head, should be easy, though. Best regards, jj

How about: Repeat 1. Express in binary the absolute value of (the sum of the even places minus the sum of the odd places) until a fixed point is reached. If it's 0, you can divide by 3; else not. ? —Dan

On May 24, 2016, at 11:04 AM, Victor Miller <victorsmiller@gmail.com> wrote:

Dan, Sure. Use the fact that 2^2 = 1 mod 3, so you "cast out 3's" -- take pairs of digits in binary, and add them up, and repeat the process as long as you have more than 2 bits.

For example 27 = 11011, so 11011 --> 1 + 10 + 11 = 110 --> 1 + 10 = 11, which is 3.

Victor

On Tue, May 24, 2016 at 1:52 PM, Dan Asimov <dasimov@earthlink.net> wrote:

...

Zak, good question: Is there a quick way to detect multiples of 3 expressed in base 2 ??? Let's see:

(2 + 1) (2^a + 2^b + ... + 2^c) =

2^(a+1) + 2^a + 2^(b+1) + 2^b + ... + 2^(c+1) + 2^c.

Hmm, if all these exponents are distinct, this pattern seems very easy to detect.

But what if some of the exponents are equal?

I bet there's a simple algorithm to untangle them.

But I may be wrong.

—Dan

...

On May 24, 2016, at 9:56 AM, Zak Seidov via math-fun < math-fun@mailman.xmission.com> wrote:

Also, in our native, base - 10, numbers divisible by 3 has sum of digits also divisible by 3, while base - 2 has nothing similar.

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

For Allan's binary version see A272679, A272680, A272681.