[seqfan] Re: Fw: NEW SEQ A164772

[David Radcliffe]

Wow, this is great stuff! I'm going to implement these ideas this
weekend and see how far I can get.

David

On Fri, Aug 28, 2009 at 10:54 AM, David Wilson<dwilson at gambitcomm.com> wrote:
> 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/
>>
>>
>
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>