mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2017-03-07, 00:36   #1
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

2×3×53 Posts
Post 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.
carpetpool is offline   Reply With Quote
Old 2017-03-07, 02:01   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

836910 Posts
Default

Quote:
Originally Posted by carpetpool View Post
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
science_man_88 is offline   Reply With Quote
Old 2017-03-07, 03:14   #3
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2×2,969 Posts
Default

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.
CRGreathouse is offline   Reply With Quote
Old 2017-03-07, 05:55   #4
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22·7·11·29 Posts
Default

Quote:
Originally Posted by carpetpool View Post
gcd(10, 46, 516, 517) = 2
Oh?
LaurV is offline   Reply With Quote
Old 2017-03-07, 06:41   #5
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

2·3·53 Posts
Default

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

gcd(10, 46, 516) = 2.
carpetpool is offline   Reply With Quote
Old 2017-03-09, 05:45   #6
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

134628 Posts
Cool

Quote:
Originally Posted by carpetpool View Post
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
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
A useful template for functions gcd() and totient(). JM Montolio A Miscellaneous Math 8 2018-02-28 15:23
Fun with the Lucky Numbers of Euler ewmayer Probability & Probabilistic Number Theory 0 2015-10-18 01:37
Coprime matrix little puzzle Damian Puzzles 18 2012-12-08 19:01
Bernoulli and Euler numbers (Sam Wagstaff project) fivemack Factoring 4 2008-02-24 00:39
euler's totient function toilet Math 1 2007-04-29 13:49

All times are UTC. The time now is 01:54.

Thu Nov 26 01:54:29 UTC 2020 up 76 days, 23:05, 3 users, load averages: 1.19, 1.24, 1.30

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.