mersenneforum.org Consecutive numbers not coprime to Euler's totient...
 Register FAQ Search Today's Posts Mark Forums Read

 2017-03-07, 00:36 #1 carpetpool     "Sam" Nov 2016 5·67 Posts Consecutive numbers not coprime to Euler's totient... What is the smallest number p such that 1000 (or 100) consecutive integers after p (if they exist), with each number k in the range p, p+1000 holds one or both of the following conditions: gcd(phi(k), k) > 1 and or (if k is odd) for each divisor d | k with d > 1, gcd(d-1, k-1) > 2 For instance, numbers from 3 to 14 hold this condition, and the smallest number of the form 12x+1 that does not hold any of the two conditions is 517 = 11*47 gcd(460, 517) = 1 gcd(10, 46, 516, 517) = 2 It is difficult (even with a program) to come up with long lists of consecutive integers holding one or two of the conditions stated above. More information, or help is appreciated. Thanks.
2017-03-07, 02:01   #2
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

24×3×52×7 Posts

Quote:
 Originally Posted by carpetpool What is the smallest number p such that 1000 (or 100) consecutive integers after p (if they exist), with each number k in the range p, p+1000 holds one or both of the following conditions: gcd(phi(k), k) > 1 and or (if k is odd) for each divisor d | k with d > 1, gcd(d-1, k-1) > 2 For instance, numbers from 3 to 14 hold this condition, and the smallest number of the form 12x+1 that does not hold any of the two conditions is 517 = 11*47 gcd(460, 517) = 1 gcd(10, 46, 516, 517) = 2 It is difficult (even with a program) to come up with long lists of consecutive integers holding one or two of the conditions stated above. More information, or help is appreciated. Thanks.
well the second one is held by all values that are of form ax+1 with only form ax+1 divisors a>2 ( and including all odd primes by default) for differing values for x ( too lazy to come up with new variables for that example) and the first one also I believe phi is multiplicative ( meaning if n=p*q, phi(n)=phi(p)*phi(q)) so if you can find the divisors to test the second one you can use their phi values to test the first as gcd with these smaller values must have that same property for at least one divisor.

Last fiddled with by science_man_88 on 2017-03-07 at 02:12

 2017-03-07, 03:14 #3 CRGreathouse     Aug 2006 5,987 Posts An easy upper bound for the first instance of N consecutive numbers k with gcd(phi(k), k) > 1 is prime(1)^2 * prime(2)^2 * ... * prime(k)^2 = (prime(k)#)^2 by the chinese remainder theorem. That's a bound of Code: 22202291863104539982614568929477487998395967183061019783574908609144463156099179608531424816705910832075940038285799824013595145823868528669077054192104709684540584321076781342024569998832239581022274701475257882978154095939510411218014891521209157908738675165724652896892317081448261367656145489554961425349281345227485318559038194778111598724542195847729105373565694770176364061433688149309396320795588096922084076693565646870559146588100 or about 10^439. This can be improved to Code: 1025874665514852208087247207970566896594614678496135433139672459523164202852297449329857531239032146527617751939701397622428668885793063475849039566685842070472 or about 10^159 with a bit of tweaking. This value should work exactly, it's not just a bound. On the flip side I checked that no 100 consecutive numbers below 10^10 have this property or the other one.
2017-03-07, 05:55   #4
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

2·31·163 Posts

Quote:
 Originally Posted by carpetpool gcd(10, 46, 516, 517) = 2
Oh?

2017-03-07, 06:41   #5
carpetpool

"Sam"
Nov 2016

5·67 Posts

Quote:
 Originally Posted by LaurV Oh?
Thanks for pointing that out LaurV, too late to edit, but it should be:

gcd(10, 46, 516) = 2.

2017-03-09, 05:45   #6
CRGreathouse

Aug 2006

5,987 Posts

Quote:
 Originally Posted by carpetpool What is the smallest number p such that 1000 (or 100) consecutive integers after p (if they exist), with each number k in the range p, p+1000 holds one or both of the following conditions: gcd(phi(k), k) > 1 and or (if k is odd) for each divisor d | k with d > 1, gcd(d-1, k-1) > 2 For instance, numbers from 3 to 14 hold this condition, and the smallest number of the form 12x+1 that does not hold any of the two conditions is 517 = 11*47 gcd(460, 517) = 1 gcd(10, 46, 516, 517) = 2 It is difficult (even with a program) to come up with long lists of consecutive integers holding one or two of the conditions stated above. More information, or help is appreciated. Thanks.
I do believe I've found the first instance of a run of length 100:
Code:
38262928110: gcd(phi(n), n) = 330
38262928111: ["gcd(38262928111-1,n-1) = 38262928110"]
38262928112: gcd(phi(n), n) = 16
38262928113: gcd(phi(n), n) = 9
38262928114: gcd(phi(n), n) = 2
38262928115: gcd(phi(n), n) = 5
38262928116: gcd(phi(n), n) = 84
38262928117: ["gcd(103-1,n-1) = 6", "gcd(371484739-1,n-1) = 6", "gcd(38262928117-1,n-1) = 38262928116"]
38262928118: gcd(phi(n), n) = 2
38262928119: gcd(phi(n), n) = 3
38262928120: gcd(phi(n), n) = 424
38262928121: ["gcd(11-1,n-1) = 10", "gcd(3478448011-1,n-1) = 10", "gcd(38262928121-1,n-1) = 38262928120"]
38262928122: gcd(phi(n), n) = 54
38262928123: gcd(phi(n), n) = 7
38262928124: gcd(phi(n), n) = 4
38262928125: gcd(phi(n), n) = 1415625
38262928126: gcd(phi(n), n) = 2
38262928127: ["gcd(38262928127-1,n-1) = 38262928126"]
38262928128: gcd(phi(n), n) = 256
38262928129: ["gcd(38262928129-1,n-1) = 38262928128"]
38262928130: gcd(phi(n), n) = 2
38262928131: gcd(phi(n), n) = 9
38262928132: gcd(phi(n), n) = 52
38262928133: gcd(phi(n), n) = 23
38262928134: gcd(phi(n), n) = 6
38262928135: gcd(phi(n), n) = 5
38262928136: gcd(phi(n), n) = 8
38262928137: gcd(phi(n), n) = 3
38262928138: gcd(phi(n), n) = 94
38262928139: ["gcd(38262928139-1,n-1) = 38262928138"]
38262928140: gcd(phi(n), n) = 36
38262928141: ["gcd(37-1,n-1) = 36", "gcd(14563-1,n-1) = 18", "gcd(71011-1,n-1) = 90", "gcd(538831-1,n-1) = 90", "gcd(2627407-1,n-1) = 18", "gcd(1034133193-1,n-1) = 36", "gcd(38262928141-1,n-1) = 38262928140"]
38262928142: gcd(phi(n), n) = 2
38262928143: gcd(phi(n), n) = 33
38262928144: gcd(phi(n), n) = 16
38262928145: ["gcd(5-1,n-1) = 4", "gcd(13-1,n-1) = 4", "gcd(65-1,n-1) = 16", "gcd(4177-1,n-1) = 16", "gcd(20885-1,n-1) = 4", "gcd(54301-1,n-1) = 4", "gcd(140929-1,n-1) = 16", "gcd(271505-1,n-1) = 16", "gcd(704645-1,n-1) = 4", "gcd(1832077-1,n-1) = 4", "gcd(9160385-1,n-1) = 16", "gcd(588660433-1,n-1) = 16", "gcd(2943302165-1,n-1) = 4", "gcd(7652585629-1,n-1) = 4", "gcd(38262928145-1,n-1) = 38262928144"]
38262928146: gcd(phi(n), n) = 6
38262928147: ["gcd(38262928147-1,n-1) = 38262928146"]
38262928148: gcd(phi(n), n) = 4
38262928149: gcd(phi(n), n) = 81
38262928150: gcd(phi(n), n) = 50
38262928151: gcd(phi(n), n) = 7
38262928152: gcd(phi(n), n) = 8
38262928153: ["gcd(937-1,n-1) = 24", "gcd(4289-1,n-1) = 8", "gcd(9521-1,n-1) = 8", "gcd(4018793-1,n-1) = 8", "gcd(8921177-1,n-1) = 8", "gcd(40835569-1,n-1) = 24", "gcd(38262928153-1,n-1) = 38262928152"]
38262928154: gcd(phi(n), n) = 22
38262928155: gcd(phi(n), n) = 15
38262928156: gcd(phi(n), n) = 4
38262928157: ["gcd(38262928157-1,n-1) = 38262928156"]
38262928158: gcd(phi(n), n) = 18
38262928159: ["gcd(577-1,n-1) = 18", "gcd(66313567-1,n-1) = 18", "gcd(38262928159-1,n-1) = 38262928158"]
38262928160: gcd(phi(n), n) = 32
38262928161: gcd(phi(n), n) = 3
38262928162: gcd(phi(n), n) = 2
38262928163: ["gcd(38262928163-1,n-1) = 38262928162"]
38262928164: gcd(phi(n), n) = 12
38262928165: gcd(phi(n), n) = 35
38262928166: gcd(phi(n), n) = 2
38262928167: gcd(phi(n), n) = 9
38262928168: gcd(phi(n), n) = 8
38262928169: ["gcd(97-1,n-1) = 8", "gcd(12197-1,n-1) = 4", "gcd(32341-1,n-1) = 4", "gcd(1183109-1,n-1) = 4", "gcd(3137077-1,n-1) = 4", "gcd(394463177-1,n-1) = 8", "gcd(38262928169-1,n-1) = 38262928168"]
38262928170: gcd(phi(n), n) = 10
38262928171: gcd(phi(n), n) = 13
38262928172: gcd(phi(n), n) = 4
38262928173: gcd(phi(n), n) = 3
38262928174: gcd(phi(n), n) = 2
38262928175: gcd(phi(n), n) = 5
38262928176: gcd(phi(n), n) = 144
38262928177: gcd(phi(n), n) = 79
38262928178: gcd(phi(n), n) = 2
38262928179: gcd(phi(n), n) = 3
38262928180: gcd(phi(n), n) = 4
38262928181: ["gcd(33811-1,n-1) = 10", "gcd(1131671-1,n-1) = 10", "gcd(38262928181-1,n-1) = 38262928180"]
38262928182: gcd(phi(n), n) = 6
38262928183: ["gcd(4801-1,n-1) = 6", "gcd(7969783-1,n-1) = 6", "gcd(38262928183-1,n-1) = 38262928182"]
38262928184: gcd(phi(n), n) = 8
38262928185: gcd(phi(n), n) = 3
38262928186: gcd(phi(n), n) = 2
38262928187: gcd(phi(n), n) = 11
38262928188: gcd(phi(n), n) = 12
38262928189: ["gcd(38262928189-1,n-1) = 38262928188"]
38262928190: gcd(phi(n), n) = 2
38262928191: gcd(phi(n), n) = 3
38262928192: gcd(phi(n), n) = 64
38262928193: gcd(phi(n), n) = 7
38262928194: gcd(phi(n), n) = 18
38262928195: gcd(phi(n), n) = 5
38262928196: gcd(phi(n), n) = 4
38262928197: gcd(phi(n), n) = 3
38262928198: gcd(phi(n), n) = 22
38262928199: ["gcd(38262928199-1,n-1) = 38262928198"]
38262928200: gcd(phi(n), n) = 4200
38262928201: ["gcd(313-1,n-1) = 24", "gcd(727-1,n-1) = 6", "gcd(168151-1,n-1) = 150", "gcd(227551-1,n-1) = 150", "gcd(52631263-1,n-1) = 6", "gcd(122245777-1,n-1) = 24", "gcd(38262928201-1,n-1) = 38262928200"]
38262928202: gcd(phi(n), n) = 2
38262928203: gcd(phi(n), n) = 9
38262928204: gcd(phi(n), n) = 4
38262928205: gcd(phi(n), n) = 5
38262928206: gcd(phi(n), n) = 6
38262928207: ["gcd(7-1,n-1) = 6", "gcd(271-1,n-1) = 6", "gcd(1897-1,n-1) = 6", "gcd(20170231-1,n-1) = 6", "gcd(141191617-1,n-1) = 6", "gcd(5466132601-1,n-1) = 6", "gcd(38262928207-1,n-1) = 38262928206"]
38262928208: gcd(phi(n), n) = 16
38262928209: gcd(phi(n), n) = 33
Would anyone care to verify?

In fact, you can even extend this by one, making this a run of length 101:
38262928210: gcd(phi(n), n) = 2

 Similar Threads Thread Thread Starter Forum Replies Last Post JM Montolio A Miscellaneous Math 8 2018-02-28 15:23 ewmayer Probability & Probabilistic Number Theory 0 2015-10-18 01:37 Damian Puzzles 18 2012-12-08 19:01 fivemack Factoring 4 2008-02-24 00:39 toilet Math 1 2007-04-29 13:49

All times are UTC. The time now is 18:20.

Wed Sep 28 18:20:38 UTC 2022 up 41 days, 15:49, 1 user, load averages: 1.88, 1.41, 1.21