Browse Prior Art Database

ON ULAM'S PROBLEM

IP.com Disclosure Number: IPCOM000128352D
Original Publication Date: 1973-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 5 page(s) / 21K

Publishing Venue

Software Patent Institute

Related People

Richard Dunn: AUTHOR [+3]

Abstract

Use of a computer is described in an attempted solution of a currently unsolved problem known as "Ulam's Problem." Although no solution was found, several patterns and regularities were found which would be useful in an at-tempted solution.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 27% of the total text.

Page 1 of 5

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

ON ULAM'S PROBLEM

by Richard Dunn Department of Computer Science University of Colorado Boulder, Colorado

Report #CU-CS-011-73 January 1973

I *.This work supported by N.S.F. Grant GJ-660.

ABSTRACT:

Use of a computer is described in an attempted solution of a currently unsolved problem known as "Ulam's Problem." Although no solution was found, several patterns and regularities were found which would be useful in an at-tempted solution.

1. The Problem

A sequenc6 As: to be generated by -the following rules:

1. Choose the initial value no as an integer greater than 1.

2 a) If an element of the sequence ni is 12 terminate the sequence.

b) Otherwise., if element ni is odd., set element

(Equation Omitted)

and repeat step 2. ni c) If element ni is even., set

(Equation Omitted)

and repeat stop 2.

some_exmawples of-sequences would be:

(Equation Omitted)

(Equation Omitted)

The problem is then stated as: Is the sequence finite in length for any choice of no? The attempt for solution to the problem proceeds in both directions--a search for an nO which gives an infinite sequence., and a search for a proof that all sequences are finite.

II. Method I - Direct, Solution

University of Colorado Page 1 Dec 31, 1973

Page 2 of 5

ON ULAM'S PROBLEM

Before attempting any more elegant approaches., it seemed worthwhile to simply try a large number of no values. Since the generating algorithm

is so simple for the sequences, a computer can be programmed to check a large number of cases very quickly. Befor4 actually writing the program, some simplifying information may be developed;

1. If we select-n() values in increasing order., we need only verify that each no value has some value in its sequence n, which is less than no in order to guarantee that the sequence is finite. Since rt. L< no., we have already tested the sequence beginning with ni 2. Using the above,, it is clear that the smallest no which gives a solution will not be even., since an even no immediately goes to no/2 according to rule'2e.

3. Ohecking a few valnes of no will show that values of the form 4k+l., k~tO.. will always give a terminating sequence by the steps 4k+l., 12k+42 6k+2,l 3k+l. (At this point, a value less than the original 4k+1 has been obtained.) other categories of values can be found., but they are only productive up to a point in eliminating cases to be tried because it becones complicated to check for each form*

Using the above simplifications., a program was written in assembly lan,zua--e~ for the GDG 640D, to, c-heck for, solutions. A.

(Equation Omitted)

used follows, As shown., there isno, exit.. from the-program;,,it was stm-ply allotted an amount of time and run unti.1 the time was exhaustedj, at which point the values of variables were checked to ensure that no solution had been found. Using this program, it was determined that if az~y no does give an infinite sequence, it must exceed 28 882 247. This was...