Numerical analysis of the first several hundred n suggests the following inequality:
$\varphi(3^n-2) \ge 2\cdot3^{n-1}$
$\begingroup$
$\endgroup$
12
-
$\begingroup$ Up to a small additive factor, your inequality says that if $p_1,\dots,p_k$ are distinct primes dividing a number of the form $3^n-2$, then $(1-p_1^{-1})\cdots(1-p_k^{-1})\ge2/3$. I suspect this is an instance of mathoverflow.net/questions/120514 . $\endgroup$– Emil JeřábekCommented Feb 7, 2013 at 14:09
-
$\begingroup$ I can't see the connection to mathoverflow.net/questions/120514? $\endgroup$– Werner AumayrCommented Feb 7, 2013 at 14:18
-
2$\begingroup$ The connection is only vague, just that some things are just naturally expected to be somewhat rare, a couple of hundreds is not much to test. In particular, you need an n such that 3^n - 2 is divisible by primes such that Emil J.'s product is less than 2/3. The only reason this is an issue at all is that you cannot have 2 and 3 for obvious reasons, neiter 11 nor 13, and also not 5 and 7 at the same time. So things get a bit large. Calculations got slightly too complex for me for just doing them so, but with Emil J. idea and some calculation with congruences one should find a counter ex. $\endgroup$– user9072Commented Feb 7, 2013 at 15:07
-
$\begingroup$ It seems not to hold for n=1. Also, if you find a counterexample, both Emil's k and your n will be substantially larger than a thousand. Gerhard "Ask Me About System Design" Paseman, 2013.02.07 $\endgroup$– Gerhard PasemanCommented Feb 7, 2013 at 15:59
-
2$\begingroup$ @Gerhard Paseman: now while I might have been a bit too optimistic regarding how easy or not it is to find a counterexample but that one would need substantially more than a thousand different primes (the k) seems unlikely to me. Did you really mean this? $\endgroup$– user9072Commented Feb 7, 2013 at 16:09
|
Show 7 more comments
1 Answer
$\begingroup$
$\endgroup$
5
Take $n=382315009082231724951830011$. Then $3^n-2$ is divisible by the primes $5, 19, 23, 47, 71, 97, 149, 167, 173, 263, 359, 383, 389, 461, 479, 503, 557$. Furthermore, $\varphi(3^n-2)<2/3\cdot(3^n-2)<2\cdot 3^{n-1}$.
The following Sage code verifies this examples. I believe that this is close to a minimal counterexample.
sage: n=382315009082231724951830011 sage: l=[5, 19, 23, 47, 71, 97, 149, 167, 173, 263, 359, 383, 389, 461, 479, 503, 557] sage: set(3.powermod(n,p) for p in l) set([2]) sage: prod(1-1/p for p in l).n() 0.666250824539016
As there are some speculations about how to find such an example, here is the (not really clever) Sage code which greedily collects the congruences for $n$ which do not contradict each other:
p,n,Q = 5,3,4
lp = [p]
s = 1-1/p
while True:
p=p.next_prime()
e=IntegerModRing(p)(3).multiplicative_order()
l=[z for z in [1..e-1] if 3.powermod(z,p) == 2]
if len(l) == 0:
continue
b=l[0]
if (b-n) % e.gcd(Q) != 0:
continue
QQ=Q.lcm(e)
n=CRT_list([n,b],[Q,e]) % QQ
Q=QQ
s*=(1-1/p)
lp.append(p)
print p,s.n()
if 2/3>s:
print n,lp
break
answered Feb 7, 2013 at 17:46
-
$\begingroup$ I would like the answer more if I had a good lower bound on k, the number of distinct prime factors of the counterexample. Can you at least trial divide by candidates up to 3^20 or even perhaps 3^50 to get an idea? Gerhard "Would Be Ever So Grateful" Paseman, 2013.02.07 $\endgroup$ Commented Feb 7, 2013 at 20:51
-
$\begingroup$ Thanks for this answer! After I initially saw the question I got quite curious what would be the outcome. Did you also try what happens if you start with 7 insted of 5? I would be quite curious how it compares. ps for Gerhard Paseman: regarding the k again, it occurs to me we were also talking about somewhat different things (which is my fault) but to me the k here is seventeen, if I counted right in any case the number of primes one had to take into account. But sure the 'rest' seems huge so there might be quite a few additional factors 'hiding'. $\endgroup$– user9072Commented Feb 7, 2013 at 21:38
-
2$\begingroup$ @Gerhard: I believe there is no way to factor $3^n-2$, this number has more that $10^{26}$ decimal digits! @quid: Indeed, if one starts with $7$, things look quite differently. Up to $p<70000$, this greedy approach yields $425$ compatible primes, starting with $7, 17, 23, 47, 71, 167,\ldots$, yet the product of the $1-1/p$ for these primes is still bigger than $0.692$. $\endgroup$ Commented Feb 7, 2013 at 22:40
-
$\begingroup$ Ah. We are, and I mistook Emil's k for omega(n). My mistake. Indeed Emil's k can be two digits. My k is omega(n), and for every such counterexample, my gut says my k has more than two digits. Peter, I was hoping you would compute it mod p for a few million choice primes p, but it is not as important now. Gerhard "Not Quite The Omega Man" Paseman, 2013.02.07 $\endgroup$ Commented Feb 7, 2013 at 23:01
-
$\begingroup$ @Peter Mueller: thank you for this additional information. I'd guessed the situations are more similar. $\endgroup$– user9072Commented Feb 7, 2013 at 23:43