Square that ends in 269696

[B+]

I saw this at LB forum posted under Rosetta Code and things only LB could do:

   '   http://rosettacode.org/wiki/Babbage_problem

   '   Charles Babbage, gave this example:
   '   What is the smallest positive integer whose square ends in the digits 269,696 ?

   '   He thought the answer might be 99,736, whose square is 9,947,269,696; but he couldn't be certain.

   n = 1

   do
       n = n + 1
   loop until right$( str$( n^2), 6) ="269696"

   '   loop until ( n^2 mod 1000000) = 269696
   '   cf BBC BASIC answer should be using mod not div- copied by a Python user??

   print "Smallest number whose square ends in ...269696 is "; n
   print "Its square is "; n^2

JB can do it too!


It made me curious about QB64 code:
_TITLE "Find the number which squared ends in ...269696"
DIM n AS _INTEGER64
DO
   n = n + 1
   IF (n * n) MOD 269696 = 0 THEN PRINT n, n * n, (n * n) MOD 269696
LOOP UNTIL n = 30000

n = 25264
PRINT "The correct number is:"; n; " squared is"; n * n



OMG! QB64 sucks at this!

This
right$( str$( n^2), 6) ="269696" Doesn't work because of E notation and the above with MOD doesn't work because it can't do MOD with numbers that high.

So I post a challenge at QB64 forum and the hero of this story is math or someone clever with it.

William F Barnes posts this beauty:

Nevermind all that bplus, I got you. Watch:

Quote
Find the lowest number which squared ends in ...269696

So I write:

x^2 = A + 269696 ,

for some unknown x and A, and I also know that A = B * 10^6 for some unknown integer B. So:

x^2 = B * 10^6 + 269696

The task is NOT to scan over all x going way into the thousands, but scan over integers B, which only go into the 100s. Then look for x to be an integer as well. Run this code...

Code: QB64: [Select]
DIM x AS DOUBLE
FOR b = 1 TO 1000
x = SQR(b * 10 ^ 6 + 269696)
IF x = INT(x) THEN EXIT FOR
NEXT
PRINT b
PRINT x
PRINT x ^ 2

... get B = 638 and x = 25264.

And we're done.

25264^2 = 638269696

Well I was impressed It might actually find answer faster in our Basics here too!

Indeed it does!FOR b = 1 TO 1000
   x = SQR(b * 10 ^ 6 + 269696)
   IF x = INT(x) THEN EXIT FOR
NEXT
PRINT b
PRINT x
PRINT x ^ 2

[tsh73]

Hello B+
Qbasic64 code you posted first is plain wrong.
It should not be IF (n * n) MOD 269696 = 0
but rather IF a * a MOD 1000000 = 269696

and as is it works in ordinary QBasic with long (32 bit) numbers
CLS
DIM a AS LONG
FOR a = 1 TO 30000
  IF a * a MOD 1000000 = 269696 THEN PRINT a: END
NEXT

[B+]

Hello B+
Qbasic64 code you posted first is plain wrong.

Oh man it's even written correctly in code I copied from LB! OK thanks tsh73  yes it works fine in QB64 also, what was I thinking (I wasn't).
 
Mr Barnes solution should arrive at the answer quicker. 

[Rod]

We should all feel perfectly free to participate in the Rosetta Code project. If any of the tasks interest you and you can code a solution in Just BASIC it will run perfectly well in Liberty BASIC. A lot of solutions delve into API code. I'm not a huge fan of that. Native is best.

If you have a solution it would be nice to see it here. Start a new thread for each task.

[tenochtitlanuk]

Anatoly- It was the posting of code in another dialect of Carl's LB that worried me- not having its extended formatting command meant the displayed answers were confusing.
I know well how close JB is to LB in capabilities. But some interesting points raised in this thread.
And I commented on other language oddities. I never used QB.

Rod- not sure that many LB RC entries use API/DLLs. For things like fill it is stupid to re-invent a 'wheel' available to us in 'native LB', especially when we've had faulty versions and it will always be so slow.

And I agree that when Chris took responsibility for transferring our discussed version onto RC it worked well.

PS off to Scotland for a week. Will wave as I pass!!

JohnF

[B+]

This confirms the faster method:
s = time$("ms")
n = 1
do
   n = n + 1
loop until right$( str$( n^2), 6) ="269696"
e = time$("ms")
print "In "; e-s;" ms, "
print "smallest number whose square ends in ...269696 is "; n
print "squared is "; n^2;" using brute force method."
print: print
s = time$("ms")
FOR b = 1 TO 1000
   x = SQR(b * 1000000 + 269696)
   IF x = INT(x) THEN EXIT FOR
NEXT
e = time$("ms")
print "In ";e-s;" ms,"
print "smallest number whose square ends in ...269696 is ";x
print "squared is ";x ^ 2;" using SQR method."


Output:

In 375 ms,
smallest number whose square ends in ...269696 is 25264
squared is 638269696 using brute force method.


In 0 ms,
smallest number whose square ends in ...269696 is 25264
squared is 638269696 using SQR method.

[B+]

OK I've generalized the program now go in search of number endings like ...999998000001 (5 nines and 5 zeros):

'Find n st squared has last digits of...  b+ 2020-02-21

do
   scan
   cls
   input "Enter a number to find the first square to end with those digits (0 quits) > ";inp
   if inp = 0 then end
   endDigits$ = str$(inp)
   nDigits = len(endDigits$)

   s = time$("ms")
   n = 0
   do
       scan
       n = n + 1
       if n mod 1000 = 0 then locate 1, 20 : print n 'progress
       if n = 1000001 then exit do
   loop until right$(str$(n^2), nDigits) = endDigits$
   e = time$("ms")
   locate 1, 2
   if n >= 1000001 then
       print "Could not find a number <= 1000000 whose square ended in ";endDigits$;" using brute force method."
   else
       print "In "; e-s;" ms, "
       print "smallest number whose square ends in ...";endDigits$;" is "; n
       print "squared is "; n^2;" using brute force method."
   end if

   s = time$("ms")
   FOR b = 0 TO 100000
       scan
       x = SQR(b * 10 ^ nDigits + inp)
       if b mod 100 = 0 then locate 1, 21 : print b 'progress
       IF x = INT(x) THEN EXIT FOR
   NEXT
   e = time$("ms")
   locate 1, 6
   if b > 100000 then
       print "Could not find a number < 1000001 whose square ended in ";endDigits$;" using SQR method."
   else
       e = time$("ms")
       print "In ";e-s;" ms,"
       print "smallest number whose square ends in ...";endDigits$;" is ";x
       print "squared is ";x ^ 2;" using SQR method."
   end if

   input " Enter q (or any) to quit, just enter to continue..."; again$
loop until len(again$)


[Enzo]

I've done a long run time experiment a long time ago of prime numbers and the 26969 pattern follows many (most) primes for while as in 100s of ,000, if I remember correctly

With a library it is possible to compress files better then .rar of any file, if you can create the correct "Qcode" sort of library to match up primes with nearest byte file data, I believe we had a decent start past or equal to .zip files although I hardly looked at my code that was edited by another user

This program seems to be right on the lines of including the same code



~ Enzo