[seqfan] Re: Fw: NEW SEQ A164772

[David Wilson]

One thing you might consider:

Let n^2 have d digits.

Then sod(n^2) = 8d.

This gives

sod(n^2) == 8d (mod 9)

which is to say

n^2 == 8d (mod 9)

This means you only have to check the following combinations of d and n:

d mod 9   n mod 9

0         0,3,6
2         4,5
5         2,7
8         1,8

This will reduce your work by a factor of 9.

There is another way to further reduce your work considerably, I call it 
the "skipping method", but it is difficult to program.

// Print all elements (squares) with d digits
sub print(int d) {

	// If we know d has no solution, quit
	if (d mod 9 !== 0, 2, 5 or 8) return;

	// Let S be the set of squares
	// Let T be the set of numbers with digit sum 8d
	// We want the intersection of these sets

	// While x is a d-digit number
	for (x = 10^(d-1); x < 10^d; ) {

		// Set y to the smallest element of S >= x (next square)
		y = ceil(sqrt(x))^2;

		// Set x to smallest element of T >= x
		x = T_elem_ge(y);

		// If these match
		if (x == y) {

			// We have found a suitable square
			print sqrt(x);

			// Continue search at x+1		
			x = x+1;
		}
	}
}

The difficult but rewarding part is T_elem_ge(x), which gives the next 
number >= x with d digits and digit sum 8d. It is an interesting 
exercise to work out a quick way to implement this function, which I 
tell you now is possible. Once you have done this, your search can skip 
over large intervals of irrelevant numbers.

David Radcliffe wrote:
> (Re: Numbers n such that the average digit of n^2 is 8.)
> 
> I continued the search until 10^10 and found eight more terms. Here is
> the complete list so far. Are there any patterns evident?
> 
> 313,298327,9893887,197483417,282753937,314623583,315432874,
> 706399164,773303937,894303633,947047833,948675387,989938887,994987437,998398167
> 8882454614,8888194417,8943142063,9374913167,9416989417,9476286187,9949260676,9949823114
> 
> I am using a Python program for the search, and I have three
> strategies to speed up the calculations.
> 1. Squares are generated by keeping a running total of consecutive odd numbers.
> 2. The digital sums of all numbers less than 10^6 are stored in a
> lookup table. Repeated division by 10^6 is used to find the digital
> sum of a larger number.
> 3. I am actually checking whether the digital sum of (10^d - 1 - k^2)
> is equal to d, where d is the number of digits in k^2. The loop is
> aborted when the sum of digits exceeds d.
> 
> I would be interested in other ideas to accelerate the search, other
> than switching to C++. Here is my Python code.
> 
> k = 10104041174   # Starting value for search. Change to k=1 to start
> at the beginning.
> 
> pow10 = 10
> N = k**2
> digits = 1
> while pow10 <= N:
>     pow10 *= 10
>     digits += 1
> n = pow10 - 1 - N
> step = 2*k+1
> 
> block = 1000000
> import scipy
> digitsums = scipy.zeros(block,int)
> for i in xrange(1,block):
>     digitsums[i] = digitsums[i/10] + (i % 10)
> 
> while 1:
>     if n < 0:
>         pow10 *= 10
>         digits += 1
>         n = pow10 - 1 - k*k
>         print "digits = %d" % (digits)
>     m = n
>     s = 0
>     while m>0:
>         s += digitsums[m % block]
>         if s > digits:
>             break
>         m /= block
>     else:
>         if s == digits:
>             print k
>     k += 1
>     n -= step
>     step += 2
> 
> 
> _______________________________________________
> 
> Seqfan Mailing list - http://list.seqfan.eu/
> 
>