[seqfan] Re: Fw: NEW SEQ A164772
David Radcliffe
dradcliffe at gmail.com
Fri Aug 28 18:36:16 CEST 2009
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/
>
More information about the SeqFan
mailing list