Polish version    English version  
  History of OI -> I OI 1993/1994 -> Problems


 News
 About Olympic
 History of OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
Problems
 OI books
 National team
 Olympic camps
 Photo gallery
 Links
 SIO
 MAIN
Niebieskie ksi.eczki
I Olympiad in Informatics 1993/1994

Task: KWA
Author: Wojciech Rytter
The Sum of Digit Squares

II stage contest  

In the collection 100 zadań (100 Problems) by a famous Polish mathematician Hugo Steinhaus there is the following problem:

Prove that if we substitute any positive integer by the sum of squares of its digits, then we substitute the obtained new number by the sum of squares of its digits, and so on, then after a finite number of repetitions of that operation we will obtain the number 1 or 4.

Example

the sum of squares of digits of the number 89 equals 64+81=145,
the sum of squares of digits of the number 145 equals 1+16+25=42,
the sum of squares of digits of the number 42 equals 16+4=20,
the sum of squares of digits of the number 20 equals 4.

Task

  1. Justify that the following informal algorithm:
    while n<>1 and n<>4 do n:=SumOfDigitSquares(n)
    has the halting property, i.e. for every natural n it halts after some finite time.

    You are supposed to use a computer in the proof, but you certainly cannot test all the natural numbers. A justification written on a sheet of paper is an important part of the solution to the problem.

  2. Write a program that successively reads positive integers from the text file KWA.IN and for each of them generates and writes a result to the text file KWA.OUT. The result for n is a sequence of distinct numbers, beginning with n and ending with the number 1 or 4, every consecutive number of which, except the first one, is the sum of the squares of digits of the previous number in this sequence. The program should complete the task even for very big natural numbers n < 1066.

At the beginning of your program, in a comment, give your last and first name, and the number of your working stand.

The input file KWA.IN is always nonempty and contains positive integers in a decimal form (at most 66-digit ones). There is a space or a single end-of-line character between consecutive numbers, and immediately after the last number there is an end-of-file character. The data is written faultlessly and your program needs not check its correctness.

The output file KWA.OUT should contain sequences generated for the numbers read from the file KWA.IN. Consecutive numbers of every sequence should be separated by a space or a single end-of-line character. Two consecutive sequences should be separated by an empty line, and immediately after the last element of the last sequence there should be an end-of-file character. Nothing else should be written in the file.

Examples

For the file KWA.IN:

33 17 638(end-of-file character)
the file KWA.OUT should contain the sequences:
33 18 65 61 37 58 89 145 42 20 4
(empty line)
17 50 25 29 85 89 145 42 20 4
(empty line)
638 109 82 68 100 1(end-of-file character)
For the file KWA.IN:
89(end-of-file character)
the file KWA.OUT should contain one sequence:
89 145 42 20 4(end-of-file character)

Your program should look for the file KWA.IN in the current directory and create the file KWA.OUT also in the current directory. The source file containing the program written by you should be named KWA.???, where ??? are substituted by at most three-letter abbreviation of the programming language used. The same program in an executable form should be saved in a file KWA.EXE. Both the files should be stored on a hard disk and on a floppy disk.

The solution to the problem consists of a program - only one - in a source and executable form, stored, satisfying the above rules, on a hard disk and on a floppy disk. The solution should also contain a written justification that the informal algorithm formulated in the point 1 of the task has the halting property.




Print friendly version