January 2006 - mathfun@mailman.xmission.com

Re: [math-fun] Re: Digital silliness
by N. J. A. Sloane 15 Jan '06

15 Jan '06

I have not been following this discussion, but when the dust settles, please be sure to send in the sequence(s) to the OEIS! Thanks Neil

1 0

Re: [math-fun] Digital silliness
by Michael Reid 14 Jan '06

14 Jan '06

i wrote > if 0 is not in D , then it's possible to get elements of S that end > with 0 . this may not always occur, but it seems likely if the set S > is reasonably large. the rightmost 0's double with each squaring and > do not affect the other digits. thus, keeping the rightmost part of the > splitting, we get arbitrarily large numbers, unless a splitting digit > occurs as the rightmost non-zero digit. the rightmost non-zero digit converges to an idempotent modulo b (the base). so if all of these idempotent are in the splitting set D , that prevents this process from producing arbitrarily large numbers. the first interesting case appears to be b = 3 , D = { 1 } . i've tried several choices for the initial number in S , and so far all have yielded only finitely many elements in S . in this case, elements in S have only 0's and 2's in their ternary representations ("cantor numbers"??), except perhaps the starting number. from the squares of cantor numbers, we excise 0-2 strings, and can safely eliminate any rightmost 0's because they'll get removed at the next iteration. most of the resulting numbers seem to be smaller than the previous number, but there are exceptions, such as 2 0^n 2 0^{n+1} 2 (where exponents indicate that many repetitions) whose square produces this palindromic substring: 22 0^{n-1} 202 0^{n-1} 22 is there an initial number for which S is infinite in this case (b = 3, D = {1}) ? rich: ) > do you know of any examples where 0 is not in D , and you can prove ) > that S is infinite? ) Sure. Base 4, D = {3}, starting value {11001}. ) The right ends of successive squarings will be xxx11[0*]1 and xxx22[0*]1. ) This is an infinite set, as the string of internal 0s grows by one 0 with ) each 4th-powering. this generalizes to any base that's a power of 2 . any other examples where we can show that S is infinite? (a trivial one is to take the set of splitting digits to be empty.) another question: is there an example of an initial number A , and a base b , and set of splitting digits D , such that the set S is finite, but for the same A and b , but for a larger set D , the set S is infinite? too many questions, not enough answers! mike

4 5

[math-fun] New sequence
by Michael Kleber 13 Jan '06

13 Jan '06

I occasionally read the libertairan law blog "The Volokh Conspiracy", www.volokh.com. Contributor Kevan Choset posts a daily puzzle; some are mathematical, while others have answers like "this is the sequence of middle initials of US presidents". Yesterday's ( http://volokh.com/posts/1137083661.shtml ) was: What's the next number in this sequence? 13, 14, 6, 7, 12, 8, 16, 9, 13, 10, 15, 11, 12, 23, 6, 1, 2, ___ Turns out that this is just the tail of the sequence -- smart, since it begins with a whole lot of 1s. The whole thing is: 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 1, 2, 1, 1, 1, 4, 2, 2, 1, 1, 1, 1, 3, 1, 2, 1, 1, 3, 4, 1, 5, 1, 1, 4, 1, 1, 1, 1, 1, 1, 1, 2, 2, 5, 1, 1, 6, 7, 1, 1, 2, 3, 1, 2, 3, 1, 4, 1, 3, 5, 1, 2, 1, 4, 2, 4, 3, 1, 2, 8, 1, 3, 6, 1, 6, 7, 1, 2, 9, 4, 5, 3, 3, 1, 10, 6, 8, 11, 7, 9, 2, 2, 12, 8, 5, 13, 6, 7, 14, 15, 5, 2, 17, 18, 4, 8, 19, 9, 3, 9, 6, 2, 9, 2, 9, 2, 10, 2, 2, 7, 3, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4, 4, 3, 3, 3, 8, 3, 3, 3, 3, 9, 4, 4, 4, 4, 4, 10, 5, 5, 21, 3, 4, 4, 4, 5, 8, 11, 5, 22, 12, 6, 6, 5, 11, 6, 9, 7, 12, 5, 4, 5, 3, 2, 2, 4, 8, 6, 3, 2, 10, 6, 7, 3, 3, 2, 4, 4, 5, 13, 5, 7, 14, 9, 8, 11, 5, 15, 8, 10, 7, 9, 10, 11, 8, 12, 11, 13, 13, 12, 14, 13, 14, 6, 7, 12, 8, 16, 9, 13, 10, 15, 11, 12, 23, 6, 1, 2, ___ ...according to http://tinyurl.com/3zz35 -- I've disguised the source, another on-line encyclopedia, whose identity might give away the answer, so them as like can puzzle over it first. I don't recall OEIS standards well enough to know whether this qualifies for inclusion; NJAS, do as you like. Either link above will reveal the answer. --Michael Kleber -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.

1 0

Re: [math-fun] Digital silliness
by Daniel Asimov 13 Jan '06

13 Jan '06

Edwin asks: << . . . . . . Does every positive integer K appear in some square? That is, given K are there integers x,y and N such that N^2 = xKy? Integers may be expressed in any base and xKy is concatenation of x, K and y. >> Although I posted some vague mumblings addressing this yesterday, Rich later pointed out in conversation that that this amounts to nothing more than the existence of a square root. Here's one way to look at it: Given K as below and even given x as well, place the concatenation xK immediately after a decimal point to get a fraction .xK . Now just expand sqrt(.xK) to enough decimal places -- call it s = trunc(sqrt(.xK)) -- such that s^2 after the decimal point begins with xK . Then multiply everything by a high enough power of 10 so that this works with integers. Let S = (10^p)s so that S is an integer; then S^2 will have initial string xK . --Dan

1 0

[math-fun] Digital silliness
by David Wilson 12 Jan '06

12 Jan '06

For a number n, let f(n) be the set of numbers gotten by splitting n^2 at the 0 digits. For example 29648^2 = 879003904 so f(29648) = { 4, 39, 879 } Let S be the smallest set of numbers containing 2 and fixed by f. What is the largest element of S? -------------------------------- - David Wilson

3 4

Re: [math-fun] Knuth's Boolean Synthesis problem; digit silliness
by Daniel Asimov 12 Jan '06

12 Jan '06

Rich asks: << Do all such sans-0-digit strings appear somewhere in the square of a sans-0-digit number? Statistically, it seems unlikely that most such strings appear in the square of a *shorter* s0d number. This would mean that, if all s0d numbers occur in the closure of {2}, most of them are reached through a path that involves shrinking down from a larger number. Second question: Do all the s0d numbers generate the same set? Or, Do all s0d numbers generate 2? >> Thinking of a digit string s as defining s/10^p in [0,1), it's clear that by going out enough places the distance between successive squares (k+1)^2/10^2r - k^2/10^2r = (2k+1)/10^2r can be made small enough so that there exist r = r(p) sufficiently large and k = k(p,r) such that .s < k^2/10^2r < .s + 1/10^p, ensuring that s occurs as a substring of k^2. --Da

2 1

Re: [math-fun] Knuth's Boolean Synthesis problem; digit silliness
by Daniel Asimov 12 Jan '06

12 Jan '06

P.S. There was a time when some random number generators were based on using the middle 50% of the digits of square numbers. --n

1 0

Re: [math-fun] Digital silliness
by Michael Reid 12 Jan '06

12 Jan '06

> There are many ways to vary this problem, most notably by changing > the base b, the set of initial numbers A, and the set of splitting > digits, which I will call D. > > Case 1: b = 10, A = {2}, D = {1}. In this case S is infinite, containing an > infinitude of numbers of the form 6*10^k. > > Case 2: b = 10, A = {2}, D = {0,1,5}, In this case S is finite, with largest > element 6347862777922. > > Case 3: b = 10, A = {2}, D = {0}. Finiteness of S unknown. i think it is reasonable to expect the behavior to be different in the case that 0 is not in D , versus the case when 0 is in D . if 0 is in D , you will never get elements of S that end with 0 (unless they're in the initial set). if 0 is not in D , then it's possible to get elements of S that end with 0 . this may not always occur, but it seems likely if the set S is reasonably large. the rightmost 0's double with each squaring and do not affect the other digits. thus, keeping the rightmost part of the splitting, we get arbitrarily large numbers, unless a splitting digit occurs as the rightmost non-zero digit. do you know of any examples where 0 is not in D , and you can prove that S is infinite? mike

2 1

[math-fun] Knuth's Boolean Synthesis problem; digit silliness
by Schroeppel, Richard 11 Jan '06

11 Jan '06

Knuth has put his Boolean Synthesis work online in a tarball at www-cs-faculty.stanford.edu/~knuth/programs/boolchains.tgz He managed to crack one of the 7 hard functions, leaving 6 to go. My own effort at a synthesis search program isn't doing very well so far -- it runs all night on small test cases, and frequently doesn't find any synthesis at all, etc. etc. --------- Digit silliness: Re the question of whether all sans-0-digit numbers appear in the closure of {2}, a related question occurred to me: Do all such sans-0-digit strings appear somewhere in the square of a sans-0-digit number? Statistically, it seems unlikely that most such strings appear in the square of a *shorter* s0d number. This would mean that, if all s0d numbers occur in the closure of {2}, most of them are reached through a path that involves shrinking down from a larger number. Second question: Do all the s0d numbers generate the same set? Or, Do all s0d numbers generate 2? Rich

1 0

Re: [math-fun] Digital silliness
by Michael Reid 11 Jan '06

11 Jan '06

> For a number n, let f(n) be the set of numbers gotten by splitting n^2 at > the 0 digits. For example > > 29648^2 = 879003904 > > so f(29648) = { 4, 39, 879 } > > Let S be the smallest set of numbers containing 2 and fixed by f. > What is the largest element of S? [ meaning "if s in S , then f(s) is a subset of S " ] a simple depth-first search finds the 103-digit number 6748117221949113364929892272889264116674288119996291 959417364228984144237685142782381391415539921278251 in S , at generation 37. that's the largest found so far, checked through 40 generations. i will try to push the search somewhat further. mike

1 0