没有合适的资源?快使用搜索试试~ 我知道了~
collatz.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 68 浏览量
2023-06-18
13:11:39
上传
评论
收藏 1.04MB PDF 举报
温馨提示
试读
13页
collatz.pdf
资源推荐
资源详情
资源评论
The Collatz Problem
Mathematical Programming with Python
https://people.sc.fsu.edu/∼jburkardt/classes/mpp 2023/collatz/collatz.pdf
Lothar Collatz proposed it, Paul Erd¨os avoided it, Terence Tao tackled it.
“Mathematics is not yet ready for such problems.”
Paul Erd¨os, advising his student not to work on the Collatz conjecture.
“No problem is so intractable that something interesting cannot be said about it.”
Jeffrey Lagarias.
The Collatz Conjecture
• The Collatz mapping produces a new number from an old one;
• By repeatedly applying the mapping, we get a potentially infinite sequence;
• If a sequence includes the same number twice, it must have entered a loop;
• By convention, a sequence that reaches 1 is terminated (actually enters a tiny loop);
• The Collatz conjecture asserts that every Collatz sequence will terminate at 1;
• No proof has been found, but mathematicians are still attracted to the problem;
• Some simple variations of the Collatz mapping have very different behaviors.
1 The Simplest “Imposible” Problem
A friend might ask for a typical mathematical problem that an “ordinary” person could understand. They
may have heard of Fermat’s Last Theorem. However, this simply says something is not possible, and that
something is an abstract formula involving x, y, z, n that is meaningless to most people.
Some famous impossible problems like doubling the cube, the quadrature of the circle, or the trisecting of an
angle, are easier to explain and visualize, but again the average listener doesn’t understand the strict rules
imposed on these problems which mean you can’t simply trisect an angle by using a protractor to measure
it, divide by 3 and get your answer.
The Collatz problem, however, involves nothing more than straightforward arithmetic, produces a surprising
variety of unexpected results, has resisted mathematical analysis for decades, and yet can be understood by
anybody.
Despite the claim that this is a simple problem, we will have to spend rather a lot of time going over the
background. Then, given that this is an unsolved problem, we will look at mathematical and computational
ideas to characterize or visualize what is going on. We will then look at turning these ideas into Python
programs. At the end, you wil be challenged to adapt these ideas, algorithms, and programs to analyze some
variations on the original Collatz problem.
1
2 The Collatz transformation
In the 1930’s, mathematician Lothar Collatz was studying an area of number theory, in which certain
functions f(n) operate on integers to produce new integers. He realized that he could visualize this process
as a kind of directed graph. The nodes of the graph would be integers, and an arrow would be drawn from
each value n to its corresponding function value f (n). Collatz realized that in some cases, such a graph
would include loops, which would imply that, for at least one starting point n, it must be the case that
f(f(...(f(n))...)) = n. Having two ways of thinking about his problem suggested new ways to solve the
problems he was interested in.
Perhaps the simplest function he looked at is now known as the Collatz function (or mapping, or transfor-
mation). We will symbolize it by T (n), and define it as:
T (n) =
(
n
2
if n is even
3n + 1 if n is odd
. Since the output of the Collatz transformation is another integer, we can apply the transformation again
and again, producing a sequence of values. For instance, starting with n = 7, here are the first xxx terms of
the corresponding sequence:
7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 4 2 1 4 2 1 ...
and we quickly lose interest when we see that the sequence has nothing new to tell us once the values 4, 2, 1
show up. If you try other starting values for n, you will find that after a few, several, or many steps, you
reach the same three values repeating endlessly. If this is a law of the universe, then it would be very nice
to be able to prove it, or to understand why it happens!
Strictly speaking, the sequences we observe have entered an infinite loop. By convention, however, as soon
as a Collatz sequence reaches the value 1, we stop, and say the sequence has terminated after finitely many
steps. And now we are ready for a formal statement of what seems to be happening:
Conjecture 1 [The Collatz Conjecture]
For any positive starting value n, the corresponding Collatz sequence n, T (n), T (T (n)), ... will terminate at
1 in finitely many steps.
2
3 Graph theory approach
Consider the positive integers n ∈ N as nodes in a graph. For every n, draw a directed edge or “arrow”
from node n to node T (n). A graph with directed edges is known as a “directed graph” or digraph; in this
case, the result is known as the Collatz digraph. The structureof the Collatz digraph may help to illustrate
certain features of T (n). Again, we will assume that any Collatz sequence that reaches 1 must stop there.
The number of directed edges coming into a node is its indegree. THe number of directed edges leaving a
node is its outdegree. Here is a fact about the indegree and outdegree of nodes of the Collatz digraph:
Theorem 1 [Node degree of Collatz Digraph]
Every node of the Collatz Digraph has outdegree 1, except for 1, which has outdegree 0. Every node of the
Collatz Digraph has indegree 1 or 2.
Since we decided that any Collatz sequence that reaches the value 1 must stop there, it turns out that the
Collatz conjecture is equivalent to the following:
Conjecture 2 [The Collatz Conjecture #2]
Every node of the Collatz digraph is the beginning of a Collatz sequence that reaches the node 1.
A graph might contain a cycle, which is a path defined by a sequence of edges which returns to its starting
point. For a digraph, a cycle must use directed edges in the proper order. If we didn’t require Collatz
sequences to stop at 1, then the Collatz digraph would include the cycle 1 → 4 → 2 → 1. We eliminated
that cycle by forcing sequences to stop at 1.
But could there be other cycles in the digraph? And if so, what does that imply about the conjecture?
Suppose there is another cycle somewhere, that is, a starting point n 6= 1, and a sequence of directed edges
defined by the Collatz function, such that we have n → T (n) → T (T (n)) → ... → n If such a cycle exists,
then it cannot pass through the node labeled 1.
Theorem 2 [A Cycle Disproves the Conjecture]
If the Collatz digraph includes a cycle, then the Collatz Conjecture is false.
Is this the only way the graph could give us problems? Let’s use our imagination, and start at some value
n and follow the sequence. We don’t want to reach 1 (so we can disprove the Conjecture), but we also
don’t want to ever repeat a value, otherwise we form a cycle, and we already worried about that. A Collatz
sequence that never repeats a value and never reaches 1 must be of infinite length, and must eventually
involve values that are arbitrarily large. We can say such a sequence “blows up”.
Theorem 3 [An Infinite Sequence Disproves the Conjecture]
If the Collatz digraph includes an infinite sequence, then the Collatz Conjecture is false.
We can turn this all around to say:
Theorem 4 [Digraph Requirements for Collatz Conjecture]
If the Collatz digraph includes no cycles, and no infinite sequences, then the Collatz conjecture is true.
Now suppose the Collatz conjecture is true, so that every node n has a finite directed path to the node 1.
If we ignore, for a moment, the direction of the edges of the digraph, then we can say that for any pair of
nodes m and n, there is a path of edges between them. A digraph which has this property is called weakly
connected. This allows us to rephrase the conjecture yet again:
Conjecture 3 [The Collatz Conjecture #3]
The Collatz digraph is weakly connected.
You can see that the existence of a cycle, or an infinite sequence, would mean that there were some nodes
that could not be connected by a path. In fact, we can simply realize that node 1 could not be connected to
any node in a cycle, or in an infinite sequence.
3
剩余12页未读,继续阅读
资源评论
卷积神经网络
- 粉丝: 338
- 资源: 8460
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- linux常用命令大全之切换目录CD命令
- Yolov7音乐资源鸭
- 94b6c85cf1ae52d4fcdffbb7a007049c.apk
- 一个基于C语言和Keil uVision开发环境的单片机开发脚本示例,用于演示一个简单的LED闪烁程序
- 电子通信设计资料一种用方波驱动鼠标光标移动的鼠标电路的设计
- K2731T146-VB一款N-Channel沟道SOT23的MOSFET晶体管参数介绍与应用说明
- 电子通信设计资料一种用单片机制作的高频正弦波逆变器
- K209-VB一款P-Channel沟道SOT23的MOSFET晶体管参数介绍与应用说明
- 前端vue常见面试题 (附带答案) 完整版PDF.pdf
- 电子通信设计资料一种新颖的消除DC-DC中斜坡补偿影响的电路结构
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功