The 3n+1 problem

One of the unsolved problems of mathematics, that can be stated easily in simple English, is what I'll call the 3n+1 problem, although it goes by many names, mostly mathematicians who have studied it. Here is the problem:

1. Use any positive integer as a starting value. Call it x.
   
2. If x is even, then divide it by 2. In other words x=x/2. Then, go to step 4.
   
3. Otherwise, if x is odd, then triple is first and then add one. In other words, x=3x+1.
   
4. If x>1, then go back to step 2

Any starting value of x will eventually lead to 1. This has been shown for every integer up to enormous numbers. The challenge is to prove this happens for every starting value. The alternative to going to 1 would be either going up forever or getting into a loop that doesn't include 1.

Here is what happens with starting values from 1 to 100. Starting values are in highlighted cells.

1
2	1
3	10	5	16	8	4	2	1
4	2	1
5	16	8	4	2	1
6	3	10	5	16	8	4	2	1
7	22	11	34	17	52	26	13	40	20	10	5	16	8	4	2	1
8	4	2	1
9	28	14	7	22	11	34	17	52	26	13	40	20	10	5	16	8	4	2	1
10	5	16	8	4	2	1
11	34	17	52	26	13	40	20	10	5	16	8	4	2	1
12	6	3	10	5	16	8	4	2	1
13	40	20	10	5	16	8	4	2	1
14	7	22	11	34	17	52	26	13	40	20	10	5	16	8	4	2	1
15	46	23	70	35	106	53	160	80	40	20	10	5	16	8	4	2	1
16	8	4	2	1
17	52	26	13	40	20	10	5	16	8	4	2	1
18	9	28	14	7	22	11	34	17	52	26	13	40	20	10	5	16	8	4	2
	1
19	58	29	88	44	22	11	34	17	52	26	13	40	20	10	5	16	8	4	2
	1
20	10	5	16	8	4	2	1
21	64	32	16	8	4	2	1
22	11	34	17	52	26	13	40	20	10	5	16	8	4	2	1
23	70	35	106	53	160	80	40	20	10	5	16	8	4	2	1
24	12	6	3	10	5	16	8	4	2	1
25	76	38	19	58	29	88	44	22	11	34	17	52	26	13	40	20	10	5	16
	8	4	2	1
26	13	40	20	10	5	16	8	4	2	1
27	82	41	124	62	31	94	47	142	71	214	107	322	161	484	242	121	364	182	91
	274	137	412	206	103	310	155	466	233	700	350	175	526	263	790	395	1186	593	1780	890
	445	1336	668	334	167	502	251	754	377	1132	566	283	850	425	1276	638	319	958	479	1438
	719	2158	1079	3238	1619	4858	2429	7288	3644	1822	911	2734	1367	4102	2051	6154	3077	9232	4616	2308
	1154	577	1732	866	433	1300	650	325	976	488	244	122	61	184	92	46	23	70	35	106
	53	160	80	40	20	10	5	16	8	4	2	1
28	14	7	22	11	34	17	52	26	13	40	20	10	5	16	8	4	2	1
29	88	44	22	11	34	17	52	26	13	40	20	10	5	16	8	4	2	1
30	15	46	23	70	35	106	53	160	80	40	20	10	5	16	8	4	2	1
31	94	47	142	71	214	107	322	161	484	242	121	364	182	91	274	137	412	206	103
	310	155	466	233	700	350	175	526	263	790	395	1186	593	1780	890	445	1336	668	334	167
	502	251	754	377	1132	566	283	850	425	1276	638	319	958	479	1438	719	2158	1079	3238	1619
	4858	2429	7288	3644	1822	911	2734	1367	4102	2051	6154	3077	9232	4616	2308	1154	577	1732	866	433
	1300	650	325	976	488	244	122	61	184	92	46	23	70	35	106	53	160	80	40	20
	10	5	16	8	4	2	1
32	16	8	4	2	1
33	100	50	25	76	38	19	58	29	88	44	22	11	34	17	52	26	13	40	20
	10	5	16	8	4	2	1
34	17	52	26	13	40	20	10	5	16	8	4	2	1
35	106	53	160	80	40	20	10	5	16	8	4	2	1
36	18	9	28	14	7	22	11	34	17	52	26	13	40	20	10	5	16	8	4
	2	1
37	112	56	28	14	7	22	11	34	17	52	26	13	40	20	10	5	16	8	4
	2	1
38	19	58	29	88	44	22	11	34	17	52	26	13	40	20	10	5	16	8	4
	2	1
39	118	59	178	89	268	134	67	202	101	304	152	76	38	19	58	29	88	44	22
	11	34	17	52	26	13	40	20	10	5	16	8	4	2	1
40	20	10	5	16	8	4	2	1
41	124	62	31	94	47	142	71	214	107	322	161	484	242	121	364	182	91	274	137
	412	206	103	310	155	466	233	700	350	175	526	263	790	395	1186	593	1780	890	445	1336
	668	334	167	502	251	754	377	1132	566	283	850	425	1276	638	319	958	479	1438	719	2158
	1079	3238	1619	4858	2429	7288	3644	1822	911	2734	1367	4102	2051	6154	3077	9232	4616	2308	1154	577
	1732	866	433	1300	650	325	976	488	244	122	61	184	92	46	23	70	35	106	53	160
	80	40	20	10	5	16	8	4	2	1
42	21	64	32	16	8	4	2	1
43	130	65	196	98	49	148	74	37	112	56	28	14	7	22	11	34	17	52	26
	13	40	20	10	5	16	8	4	2	1
44	22	11	34	17	52	26	13	40	20	10	5	16	8	4	2	1
45	136	68	34	17	52	26	13	40	20	10	5	16	8	4	2	1
46	23	70	35	106	53	160	80	40	20	10	5	16	8	4	2	1
47	142	71	214	107	322	161	484	242	121	364	182	91	274	137	412	206	103	310	155
	466	233	700	350	175	526	263	790	395	1186	593	1780	890	445	1336	668	334	167	502	251
	754	377	1132	566	283	850	425	1276	638	319	958	479	1438	719	2158	1079	3238	1619	4858	2429
	7288	3644	1822	911	2734	1367	4102	2051	6154	3077	9232	4616	2308	1154	577	1732	866	433	1300	650
	325	976	488	244	122	61	184	92	46	23	70	35	106	53	160	80	40	20	10	5
	16	8	4	2	1
48	24	12	6	3	10	5	16	8	4	2	1
49	148	74	37	112	56	28	14	7	22	11	34	17	52	26	13	40	20	10	5
	16	8	4	2	1
50	25	76	38	19	58	29	88	44	22	11	34	17	52	26	13	40	20	10	5
	16	8	4	2	1
51	154	77	232	116	58	29	88	44	22	11	34	17	52	26	13	40	20	10	5
	16	8	4	2	1
52	26	13	40	20	10	5	16	8	4	2	1
53	160	80	40	20	10	5	16	8	4	2	1
54	27	82	41	124	62	31	94	47	142	71	214	107	322	161	484	242	121	364	182
	91	274	137	412	206	103	310	155	466	233	700	350	175	526	263	790	395	1186	593	1780
	890	445	1336	668	334	167	502	251	754	377	1132	566	283	850	425	1276	638	319	958	479
	1438	719	2158	1079	3238	1619	4858	2429	7288	3644	1822	911	2734	1367	4102	2051	6154	3077	9232	4616
	2308	1154	577	1732	866	433	1300	650	325	976	488	244	122	61	184	92	46	23	70	35
	106	53	160	80	40	20	10	5	16	8	4	2	1
55	166	83	250	125	376	188	94	47	142	71	214	107	322	161	484	242	121	364	182
	91	274	137	412	206	103	310	155	466	233	700	350	175	526	263	790	395	1186	593	1780
	890	445	1336	668	334	167	502	251	754	377	1132	566	283	850	425	1276	638	319	958	479
	1438	719	2158	1079	3238	1619	4858	2429	7288	3644	1822	911	2734	1367	4102	2051	6154	3077	9232	4616
	2308	1154	577	1732	866	433	1300	650	325	976	488	244	122	61	184	92	46	23	70	35
	106	53	160	80	40	20	10	5	16	8	4	2	1
56	28	14	7	22	11	34	17	52	26	13	40	20	10	5	16	8	4	2	1
57	172	86	43	130	65	196	98	49	148	74	37	112	56	28	14	7	22	11	34
	17	52	26	13	40	20	10	5	16	8	4	2	1
58	29	88	44	22	11	34	17	52	26	13	40	20	10	5	16	8	4	2	1
59	178	89	268	134	67	202	101	304	152	76	38	19	58	29	88	44	22	11	34
	17	52	26	13	40	20	10	5	16	8	4	2	1
60	30	15	46	23	70	35	106	53	160	80	40	20	10	5	16	8	4	2	1
61	184	92	46	23	70	35	106	53	160	80	40	20	10	5	16	8	4	2	1
62	31	94	47	142	71	214	107	322	161	484	242	121	364	182	91	274	137	412	206
	103	310	155	466	233	700	350	175	526	263	790	395	1186	593	1780	890	445	1336	668	334
	167	502	251	754	377	1132	566	283	850	425	1276	638	319	958	479	1438	719	2158	1079	3238
	1619	4858	2429	7288	3644	1822	911	2734	1367	4102	2051	6154	3077	9232	4616	2308	1154	577	1732	866
	433	1300	650	325	976	488	244	122	61	184	92	46	23	70	35	106	53	160	80	40
	20	10	5	16	8	4	2	1
63	190	95	286	143	430	215	646	323	970	485	1456	728	364	182	91	274	137	412	206
	103	310	155	466	233	700	350	175	526	263	790	395	1186	593	1780	890	445	1336	668	334
	167	502	251	754	377	1132	566	283	850	425	1276	638	319	958	479	1438	719	2158	1079	3238
	1619	4858	2429	7288	3644	1822	911	2734	1367	4102	2051	6154	3077	9232	4616	2308	1154	577	1732	866
	433	1300	650	325	976	488	244	122	61	184	92	46	23	70	35	106	53	160	80	40
	20	10	5	16	8	4	2	1
64	32	16	8	4	2	1
65	196	98	49	148	74	37	112	56	28	14	7	22	11	34	17	52	26	13	40
	20	10	5	16	8	4	2	1
66	33	100	50	25	76	38	19	58	29	88	44	22	11	34	17	52	26	13	40
	20	10	5	16	8	4	2	1
67	202	101	304	152	76	38	19	58	29	88	44	22	11	34	17	52	26	13	40
	20	10	5	16	8	4	2	1
68	34	17	52	26	13	40	20	10	5	16	8	4	2	1
69	208	104	52	26	13	40	20	10	5	16	8	4	2	1
70	35	106	53	160	80	40	20	10	5	16	8	4	2	1
71	214	107	322	161	484	242	121	364	182	91	274	137	412	206	103	310	155	466	233
	700	350	175	526	263	790	395	1186	593	1780	890	445	1336	668	334	167	502	251	754	377
	1132	566	283	850	425	1276	638	319	958	479	1438	719	2158	1079	3238	1619	4858	2429	7288	3644
	1822	911	2734	1367	4102	2051	6154	3077	9232	4616	2308	1154	577	1732	866	433	1300	650	325	976
	488	244	122	61	184	92	46	23	70	35	106	53	160	80	40	20	10	5	16	8
	4	2	1
72	36	18	9	28	14	7	22	11	34	17	52	26	13	40	20	10	5	16	8
	4	2	1
73	220	110	55	166	83	250	125	376	188	94	47	142	71	214	107	322	161	484	242
	121	364	182	91	274	137	412	206	103	310	155	466	233	700	350	175	526	263	790	395
	1186	593	1780	890	445	1336	668	334	167	502	251	754	377	1132	566	283	850	425	1276	638
	319	958	479	1438	719	2158	1079	3238	1619	4858	2429	7288	3644	1822	911	2734	1367	4102	2051	6154
	3077	9232	4616	2308	1154	577	1732	866	433	1300	650	325	976	488	244	122	61	184	92	46
	23	70	35	106	53	160	80	40	20	10	5	16	8	4	2	1
74	37	112	56	28	14	7	22	11	34	17	52	26	13	40	20	10	5	16	8
	4	2	1
75	226	113	340	170	85	256	128	64	32	16	8	4	2	1
76	38	19	58	29	88	44	22	11	34	17	52	26	13	40	20	10	5	16	8
	4	2	1
77	232	116	58	29	88	44	22	11	34	17	52	26	13	40	20	10	5	16	8
	4	2	1
78	39	118	59	178	89	268	134	67	202	101	304	152	76	38	19	58	29	88	44
	22	11	34	17	52	26	13	40	20	10	5	16	8	4	2	1
79	238	119	358	179	538	269	808	404	202	101	304	152	76	38	19	58	29	88	44
	22	11	34	17	52	26	13	40	20	10	5	16	8	4	2	1
80	40	20	10	5	16	8	4	2	1
81	244	122	61	184	92	46	23	70	35	106	53	160	80	40	20	10	5	16	8
	4	2	1
82	41	124	62	31	94	47	142	71	214	107	322	161	484	242	121	364	182	91	274
	137	412	206	103	310	155	466	233	700	350	175	526	263	790	395	1186	593	1780	890	445
	1336	668	334	167	502	251	754	377	1132	566	283	850	425	1276	638	319	958	479	1438	719
	2158	1079	3238	1619	4858	2429	7288	3644	1822	911	2734	1367	4102	2051	6154	3077	9232	4616	2308	1154
	577	1732	866	433	1300	650	325	976	488	244	122	61	184	92	46	23	70	35	106	53
	160	80	40	20	10	5	16	8	4	2	1
83	250	125	376	188	94	47	142	71	214	107	322	161	484	242	121	364	182	91	274
	137	412	206	103	310	155	466	233	700	350	175	526	263	790	395	1186	593	1780	890	445
	1336	668	334	167	502	251	754	377	1132	566	283	850	425	1276	638	319	958	479	1438	719
	2158	1079	3238	1619	4858	2429	7288	3644	1822	911	2734	1367	4102	2051	6154	3077	9232	4616	2308	1154
	577	1732	866	433	1300	650	325	976	488	244	122	61	184	92	46	23	70	35	106	53
	160	80	40	20	10	5	16	8	4	2	1
84	42	21	64	32	16	8	4	2	1
85	256	128	64	32	16	8	4	2	1
86	43	130	65	196	98	49	148	74	37	112	56	28	14	7	22	11	34	17	52
	26	13	40	20	10	5	16	8	4	2	1
87	262	131	394	197	592	296	148	74	37	112	56	28	14	7	22	11	34	17	52
	26	13	40	20	10	5	16	8	4	2	1
88	44	22	11	34	17	52	26	13	40	20	10	5	16	8	4	2	1
89	268	134	67	202	101	304	152	76	38	19	58	29	88	44	22	11	34	17	52
	26	13	40	20	10	5	16	8	4	2	1
90	45	136	68	34	17	52	26	13	40	20	10	5	16	8	4	2	1
91	274	137	412	206	103	310	155	466	233	700	350	175	526	263	790	395	1186	593	1780
	890	445	1336	668	334	167	502	251	754	377	1132	566	283	850	425	1276	638	319	958	479
	1438	719	2158	1079	3238	1619	4858	2429	7288	3644	1822	911	2734	1367	4102	2051	6154	3077	9232	4616
	2308	1154	577	1732	866	433	1300	650	325	976	488	244	122	61	184	92	46	23	70	35
	106	53	160	80	40	20	10	5	16	8	4	2	1
92	46	23	70	35	106	53	160	80	40	20	10	5	16	8	4	2	1
93	280	140	70	35	106	53	160	80	40	20	10	5	16	8	4	2	1
94	47	142	71	214	107	322	161	484	242	121	364	182	91	274	137	412	206	103	310
	155	466	233	700	350	175	526	263	790	395	1186	593	1780	890	445	1336	668	334	167	502
	251	754	377	1132	566	283	850	425	1276	638	319	958	479	1438	719	2158	1079	3238	1619	4858
	2429	7288	3644	1822	911	2734	1367	4102	2051	6154	3077	9232	4616	2308	1154	577	1732	866	433	1300
	650	325	976	488	244	122	61	184	92	46	23	70	35	106	53	160	80	40	20	10
	5	16	8	4	2	1
95	286	143	430	215	646	323	970	485	1456	728	364	182	91	274	137	412	206	103	310
	155	466	233	700	350	175	526	263	790	395	1186	593	1780	890	445	1336	668	334	167	502
	251	754	377	1132	566	283	850	425	1276	638	319	958	479	1438	719	2158	1079	3238	1619	4858
	2429	7288	3644	1822	911	2734	1367	4102	2051	6154	3077	9232	4616	2308	1154	577	1732	866	433	1300
	650	325	976	488	244	122	61	184	92	46	23	70	35	106	53	160	80	40	20	10
	5	16	8	4	2	1
96	48	24	12	6	3	10	5	16	8	4	2	1
97	292	146	73	220	110	55	166	83	250	125	376	188	94	47	142	71	214	107	322
	161	484	242	121	364	182	91	274	137	412	206	103	310	155	466	233	700	350	175	526
	263	790	395	1186	593	1780	890	445	1336	668	334	167	502	251	754	377	1132	566	283	850
	425	1276	638	319	958	479	1438	719	2158	1079	3238	1619	4858	2429	7288	3644	1822	911	2734	1367
	4102	2051	6154	3077	9232	4616	2308	1154	577	1732	866	433	1300	650	325	976	488	244	122	61
	184	92	46	23	70	35	106	53	160	80	40	20	10	5	16	8	4	2	1
98	49	148	74	37	112	56	28	14	7	22	11	34	17	52	26	13	40	20	10
	5	16	8	4	2	1
99	298	149	448	224	112	56	28	14	7	22	11	34	17	52	26	13	40	20	10
	5	16	8	4	2	1
100	50	25	76	38	19	58	29	88	44	22	11	34	17	52	26	13	40	20	10
	5	16	8	4	2	1

No particular question here but I've been wasting time on this problem lately and have made some interesting observations. I'll share them later if anyone else seems interested in this.

The question for the poll is which statements do you agree with?

Previous discussion on this: https://wizardofvegas.com/forum/questions-and-answers/math/24489-n-3x-1/

Quote: RS

Previous discussion on this: https://wizardofvegas.com/forum/questions-and-answers/math/24489-n-3x-1/

I knew this problem seemed familiar.

If you still want to talk about something that's known to be true for a significant number of numbers but not yet proven true for all of them, how about Goldbach's Conjecture - all even numbers greater than 2 can be expressed as the sum of two (not necessarily different) primes?

Meanwhile, here's a problem from the most recent Mathematical Association of America's high school math exam (worded slightly differently):

Two random numbers are chosen by a computer - A, which is uniformly chosen between 0 and 6 (note that A is not necessarily an integer), and B, which is uniformly chosen between 3 and 4. Without knowing either value of A or B in advance, what number should you choose so that the probability that your number is somewhere between A and B is maximized?

some babble I vaguely remember in Diffy Q's class:
take the integral (or derivative?) using the limit as X approaches infinity? (x --> ��� )

did I solve it? :)

edit:
hm.. this forum treats 'alt 236' ascii symbol differently

I woke up this morning thinking I'd solve a problem that has escaped all humanity to date. Here it goes...

After you do step 3, you always have an even positive number going into step 4 that is number 4 or greater... So step 3 always leads to step 2.

What I don't know how to explain is how steps 2 and 3 combined always get you to a number that is a positive power of 2... (2^x)

Once you are there, rule 2 will always get you an even result until you eventually land at number 1 which ends the loop.

Ok, I guess I didn't prove anything.

There is a whole root system of numbers that eventually lead to zero. There is a fork at every number which can be expressed as 6n+4, where n is an integer. With a fork every sixth number it is not surprising that most numbers lead to one eventually. Why none escape this root system is the question.

Quote: 100xOdds

take the integral (or derivative?) using the limit as X approaches infinity? (x --> ��� )

hm.. this forum treats 'alt 236' ascii symbol differently

"Alt-236" is "OEM ASCII" 236; it is not "Windows ASCII" 236, which is ì (and is entered with Alt-0236).

Let me try it: ∞ (that "should be" an infinity symbol)

I think geometric serieses (is that a word?) is how people way smarter than me invented calculus. I think that's what we are dealing with here, and it is notably above my pay grade.

I'll pipe down and let the smart people talk now.

Quote: prozema

I think geometric serieses (is that a word?) is how people way smarter than me invented calculus. I think that's what we are dealing with here, and it is notably above my pay grade.

I think this is a whole different branch of math than calculus. Then again, maybe you're seeing a connection that escapes me. In fact, I have a theory there is an undiscovered branch of mathematics, some kind of number theory, that would provide easy answers to lots of unanswered problems like this, especially in the realm of prime numbers.

This is the kind of thing that fascinates me.


Direct link: https://www.youtube.com/watch?v=YsaRJgm0xac

I've seen this problem before in a list of unsolved mathematical problems. I agree its fascinating, and I also agree that it is not calculus nor a geometric series.

I'll look at it when I get a free moment -then maybe I'll be ready to hear the Wiz's observations.

The geometric series occours when the number gets to an x power of 2. It always reduces to 1 after you get there. Why the number always gets to a power of 2 making a geometric reduction to 1 is the tough part to show.

If I have a geometric series that converges on 0, the sum of that series fills the area under the curve in calculus. I want to say it was a specific series, but I don't remember.

I'm might be wrong, but that's what I was thinking.

Anyway... I recall one of my masters instructors (economics) used to tell stories about a guy who got a PhD in numbers. I think he was from Denver and I'm old enough that it was before weed was legal.

where's the poll option of 'I stopped beating my wife'?

Internet research revealed that there has certainly been a lot of work on this problem. I would summarize some of the research that I surveyed as:

1. Defining a parameter that is the length of an x/2|3x+1 sequence required to converge to 1, and then studying how that length parameter varies withe the value of x. For example, the maximum length of a sequence produced by the x/2|3x+1 system when x₀ = (1 to n) is observed to increase with n in less than a linear fashion.

2. Generalizing the problem and then defining different categories of the generalized problem statement according to the characteristics of the sequences that are produced.

3. Analyzing the "cycles" or "loops" that number sequences can get into and defining different categories of these cycles/loops.

-trying to define the characteristics of a cycle that would loop forever without converging to 1 and then evaluating whether the x/2|3x+1 system could produce it.
- trying to define characteristics of x that would lead the x/2|3x+1 system to produce sequences of numbers that do not loop and generally grow in magnitude forever
- evaluating characteristics of the up/down movement of the sequences produced by x/2|3x+1 as a function of the initial value of x

4. Mapping the sequences onto graphs with elegantly-defined axes and studying the patterns that are produced.

It goes without saying that none of these approaches have yet proven or disproven the 3n+1 hypothesis, although certain categories of initial values of x have been shown to always produce sequences that terminate in 1.
*********************
I have a couple of ideas for possible approaches to analyze this problem. I want to spend a couple of hours working on them first, but then I'll share the ideas by posting them here. Naturally, I'm curious as to what the Wiz has done and would be happy to kibitz if I'm capable of it.