Sequence of non-squares: Difference between revisions
(New page: {{task}} Show that the following remarkable formula gives the [http://www.research.att.com/~njas/sequences/A000037 sequence] of non-square [http://en.wikipedia.org/wiki/Natural_number nat...) |
(Ada solution added) |
||
Line 6: | Line 6: | ||
* Show that no squares occur for n less than one million |
* Show that no squares occur for n less than one million |
||
== |
=={{header|Ada}}== |
||
<ada> |
|||
with Ada.Numerics.Long_Elementary_Functions; |
|||
with Ada.Text_IO; use Ada.Text_IO; |
|||
procedure Sequence_Of_Non_Squares_Test is |
|||
use Ada.Numerics.Long_Elementary_Functions; |
|||
function Non_Square (N : Natural) return Natural is |
|||
begin |
|||
return N + Natural (Long_Float'Floor (0.5 + Sqrt (Long_Float (N)))); |
|||
end Non_Square; |
|||
I : Natural; |
|||
begin |
|||
for N in 1..22 loop -- First 22 non-squares |
|||
Put (Natural'Image (Non_Square (N))); |
|||
end loop; |
|||
New_Line; |
|||
for N in 1..1_000_000 loop -- Check first million of |
|||
I := Non_Square (N); |
|||
if I = Natural (Sqrt (Long_Float (I))) then |
|||
Put_Line ("Found a square at:" & Natural'Image (N)); |
|||
end if; |
|||
end loop; |
|||
end Sequence_Of_Non_Squares_Test; |
|||
</ada> |
|||
Sample output: |
|||
<pre> |
|||
2 3 5 6 7 8 10 11 12 13 14 15 17 18 19 20 21 22 23 24 26 27 |
|||
</pre> |
|||
=={{header|Python}}== |
|||
<python> |
<python> |
||
>>> from math import sqrt,floor |
>>> from math import sqrt,floor |
Revision as of 09:40, 24 August 2008
You are encouraged to solve this task according to the task description, using any language you may know.
Show that the following remarkable formula gives the sequence of non-square natural numbers:
n + floor(1/2 + sqrt(n))
- Print out the values for n in the range 1 to 22
- Show that no squares occur for n less than one million
Ada
<ada> with Ada.Numerics.Long_Elementary_Functions; with Ada.Text_IO; use Ada.Text_IO;
procedure Sequence_Of_Non_Squares_Test is
use Ada.Numerics.Long_Elementary_Functions; function Non_Square (N : Natural) return Natural is begin return N + Natural (Long_Float'Floor (0.5 + Sqrt (Long_Float (N)))); end Non_Square; I : Natural;
begin
for N in 1..22 loop -- First 22 non-squares Put (Natural'Image (Non_Square (N))); end loop; New_Line; for N in 1..1_000_000 loop -- Check first million of I := Non_Square (N); if I = Natural (Sqrt (Long_Float (I))) then Put_Line ("Found a square at:" & Natural'Image (N)); end if; end loop;
end Sequence_Of_Non_Squares_Test; </ada> Sample output:
2 3 5 6 7 8 10 11 12 13 14 15 17 18 19 20 21 22 23 24 26 27
Python
<python> >>> from math import sqrt,floor >>> def nonsqr(n): return n + floor(0.5 + sqrt(n))
>>> # first 22 values (as a list) has no squares: >>> [nonsqr(i) for i in xrange(1,23)] [2.0, 3.0, 5.0, 6.0, 7.0, 8.0, 10.0, 11.0, 12.0, 13.0, 14.0, 15.0, 17.0, 18.0, 19.0, 20.0, 21.0, 22.0, 23.0, 24.0, 26.0, 27.0] >>> # The following check shows no squares up to one million: >>> for i in xrange(1,1000000): j = sqrt(nonsqr(i)) assert j != int(j), "Found a square in the sequence: %i" % i
>>>
</python>