注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ad0415的博客

欢迎来作客!ad0415@yeah.net

 
 
 

日志

 
 

http://www.ieeta.pt/~tos/3x+1.html  

2008-03-07 21:55:29|  分类: 数学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Computational verification of the 3x+1 conjecture



Introduction

Let x be an integer. Let the function T(x) be equal to (3x+1)/2 if x is odd and equal to x/2 if x is even. The 3x+1 conjecture [1], [2, problem E16] asserts that starting from any positive integer n the repeated iteration of T(x) eventually produces the integer 1, after which the iterates will alternate between the integers 1 and 2.

Let n>1 be an integer. The trajectory of n is the sequence { n, T(n), T(T(n)), ..., T^(k)(n), ... }, where T^(k)(n) denotes the k-th iterate of T(x) for an initial value of n. The stopping time of n, denoted by s(n), is the least positive integer k for which T^(k)(n)<n, if it exists, or infinity, otherwise. The maximum excursion of n, denoted by t(n), is the maximum value of the trajectory of n, if that number exists, or infinity, otherwise. In the first case m(n) denotes the smallest iterate number where the maximum occurred. Furthermore, n is a maximum excursion record-holder if t(m)<t(n) for all integers m belonging to the interval 1<m<n, and n is a stopping time record-holder if s(m)<s(n) for all integers m belonging to the interval 1<m<n.

News

September 21, 2004: 2^58 reached. Eighty two maximum excursion record-holders and thirty three stopping time record-holders.
December 16, 2004: 2·2^58 reached. Two new maximum excursion record-holders.
February 23, 2005: 3·2^58 reached. One new maximum excursion record-holder.
April 8, 2005: 4·2^58 reached. Two new maximum excursion record-holders.
May 25, 2005: 5·2^58 reached. One new stopping time record-holder.
August 2, 2005: 6·2^58 reached.
October 26, 2005: 7·2^58 reached. One new maximum excursion record-holder.
February 7, 2006: 8·2^58 reached.
March 29, 2006: 9·2^58 reached.
May 26, 2006: 10·2^58 reached. One new stopping time record-holder (the first above 1000).
October 28, 2006: 11·2^58 reached.
December 12, 2006: 12·2^58 reached.
February 1, 2007: 13·2^58 reached.
May 23, 2007: 14·2^58 reached.
November 9, 2007: 15·2^58 reached.
January 4, 2008: 16·2^58 reached.
February 21, 2008: 17·2^58 reached.

Computational results

In order to test the 3x+1 conjecture, in 1996 we wrote a computer program (in the programming language C), which computed the trajectories of all initial values of n smaller that a given limit and having a stopping time known to be larger than 40 [3]. Each run of that program tested an interval of 2^50 integers. On an otherwise idle 266MHz DEC Alpha computer, the original program tested, on the average, an interval of approximately 317 million integers each second. Elementary improvements of the verification algorithm, the most important of which was suggested by Eric Roosendaal, raised this number to around 370 million. This program was run between August 1996 and April 2000 on two 133MHz and two 266MHz DEC Alpha workstations. We stopped it when 100·2^50 was reached. Around 14.4 CPU years were used in this verification.

In the Spring of 2004 we devised an improved algorithm to test the 3x+1 conjecture, about three times faster than our previous one. Each pass of the new algorithm tests (and double-checks) an interval of 2^58 integers. The entire computation is split among several computers (currently around 20, in part time). We restarted our verification efforts in June 2004. So far, we have verified the 3x+1 conjecture up to

17·2^58 = 4899916394579099648 > 4.899·10^18.

Around 70.3 CPU years were used in this verification. Since no counter-example was found, the 3x+1 conjecture is probably true for all positive integers not larger than this verification limit. (The word probably in the previous sentence is to guard against machine or algorithm errors; we had extreme care with the latter but cannot control the former. The machines where the program was run are reasonably reliable, and since we double check all computations we have great confidence that our results are correct.) Eric Roosendaal and collaborators have independently verified the 3x+1 conjecture up to 515·2^50 (July 2007).

Our program also determines all maximum excursion and stopping time record-holders occurring inside the verification interval. In the following figure we present the maximum excursion record-holders found [3k, compressed with gzip] in the verification effort.

Graph of the maximum excursion record-holders

It is remarkable that the t(n) records are always close to n^2. Only a few are actually larger than n^2 (the blue dots). In fact, it appears that t(n)<n^2 f(n), where f(n) is either a constant or a very slowly increasing function of n. This is in agreement with the stochastic results reported in [4]. In the following figure we present the stopping time record-holders found [1k, compressed with gzip] in the verification effort.

Graph of the stopping time record-holders

Contrary to the t(n) records, the s(n) records appear to grow in a more erratic way. Nonetheless, they appear to be approximately proportional to the logarithm of n, as the stochastic models of the 3x+1 problem predict.

All record-holders between 100·2^50 and 309·2^50 were first discovered by Eric Roosendaal and his collaborators.

References

[1] Jeffrey C. Lagarias, The 3x+1 problem and its generalizations, The American Mathematical Monthly, vol. 92, no. 1, pp. 3-23, 1985.
[2] Richard K. Guy, Unsolved problems in number theory, third edition, Springer-Verlag, 2004.
[3] Tomás Oliveira e Silva, Maximum excursion and stopping time record-holders for the 3x+1 problem: computational results, Mathematics of Computation, vol. 68, no. 225, pp. 371-384, 1999.
[4] J. C. Lagarias and A. Weiss, The 3x+1 problem: two stochastic models, The Annals of Applied Probability, vol. 2, no. 1, pp. 229-261, 1992.

Additional links


Tomás Oliveira e Silva
Departamento de Electrónica, Telecomunicações e Informática
Universidade de Aveiro
3810-193 AVEIRO
PORTUGAL
     February 21, 2008
My personal logo
Phone: +351-234-370379
Fax: +351-234-370545
     Phone (internal): 23013
Office: DET 237
E-mail address: tos@ua.pt
Home page: http://www.ieeta.pt/~tos/
  评论这张
 
阅读(381)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017