Hilbert's hotel - 2020-04-06

Ante

00:19

Masterphile, so bounty is now awarded?

@Mathphile

Mathphile

@Ante yes

palindromicprime

Still working on the integral I mentioned yesterday

That to a side for now. Interesting to checkout nonethelessas a side project I’m also working on Wolfram’s rule 30 problems. But I’ve taken

Ugh StackExchange chat on iPad is worthless

Sentences loop around and I can’t even see what I’m typing

Ante

01:53

@Mathphile ?

Mathphile

what's wrong?

Ante

are you at computer

?

Mathphile

I am on my phone rn

Knight

02:18

@palindromicprime Does that follow from that?

Ante

13:34

@Peter the downvote!

-1

Q: Do only multiples of $6$ can satisfy this divisibility condition with $\sigma$ and $\varphi$?

After doing some computations of the divisibility of $\sigma(n)$ with $n+ \varphi(n)$, mostly with Peter´s help, we found these solutions: $n=2, 456, 828, 7584 ,33462 , 1357440, 1596048 ,1964544 ,19800384 ,26211264 ,31451136 ,106805184,156868224 ,316113024 ,365395680 ,449746560 ,502349274 ,50329...

arithmetic-functions

Ante

13:48

now it´s positive score

Knight

14:14

@Ante

Hello

@Peter Hello Hello Hello! Is anybody in there?

Ante

yes?

Knight

Can I do something more in this expression $$f^{-1} (x) = f \left( f(x) \right) $$?

Can I obtain something from that expression?

Ante

is f^{-1} inverse of f?

Knight

Yes

Ante

14:37

@Peter i have an idea

Knight

What about my problem Ante? :-)

Ante

i cannot solve everything

Knight

You can !

My problems are much much easier than Bell’s problem which you have aimed to solve

Peter

@Ante What is your idea ?

Ante

14:52

to compute the smallest number w(n) such that sigma(n)/(n+phi(n)+w(n)) is natural number

is that hard?

Peter

No, but this does not have a solution in general. If sigma(n) < n+phi(n) , then there is no such w(n). I think, there are some n satisfying this inequality.

Ante

then w(n) is negative in that case

Peter

OK, in this case, it works. The most efficient way is to factor sigma(n) and to look which divisor comes next to n+phi(n)

Peter

15:20

Why not determining the near misses where sigma(n) mod n+phi(n) is -1 or 1?

Ante

that is even better

Peter

Do you think you can program that ?

Ante

nope, hardly

Peter

You should try it, than you learn much. You only need the for-loop, the command mod and the functions eulerphi and sigma.

Ante

ah, hardly now, my head hurts, i have a headache

Peter

15:23

OK, I will do it ...

I abort my search for examples not divisible by 3 ...

Ante

i also stopped the procedure

Peter

? for(n=1,10^8,if(Mod(sigma(n),n+eulerphi(n))==1,print1(n," ")))
1 4 15 903

still in progress

? for(n=1,10^8,if(Mod(sigma(n),n+eulerphi(n))==-1,print1(n," ")))
1 3 21

still in progress

? for(n=1,10^8,if(Mod(sigma(n),n+eulerphi(n))==1,print1(n," ")))
1 4 15 903 28611063

more hits than near-misses !

Let us look what Haran can proof...

Do you think that the problem whether there is an odd perfect number is an example for Goedels incompleteness theorem ? Maybe independent of ZFC ?

@Ante

Ante

if they do not exist, then it can be proven

Peter

No, the other way round. If there is one, this can be proven.

? for(n=1,10^8,if(Mod(sigma(n),n+eulerphi(n))==1,print1(n," ")))
1 4 15 903 28611063
?

The other is still in progress

? for(n=1,10^8,if(Mod(sigma(n),n+eulerphi(n))==-1,print1(n," ")))
1 3 21
?

Ante

try now sigma(n)/(n+2phi(n))

Peter

15:35

no near misses, hits, right ?

Ante

yes

Peter

? for(n=1,10^8,if(Mod(sigma(n),n+2*eulerphi(n))==0,print(n," ",sigma(n)/(n+2*eulerphi(n))," ",omega(n)," ",bigomega(n)," ",factor(n))))
10 1 2 2 [2, 1; 5, 1]
44 1 2 3 [2, 2; 11, 1]
184 1 2 4 [2, 3; 23, 1]
752 1 2 5 [2, 4; 47, 1]
3796 1 3 4 [2, 2; 13, 1; 73, 1]
7320 2 4 6 [2, 3; 3, 1; 5, 1; 61, 1]
12224 1 2 7 [2, 6; 191, 1]
19488 2 4 8 [2, 5; 3, 1; 7, 1; 29, 1]
44856 2 4 7 [2, 3; 3, 2; 7, 1; 89, 1]
49024 1 2 8 [2, 7; 383, 1]
221088 2 4 9 [2, 5; 3, 1; 7, 2; 47, 1]

again only even solutions, it seems.

Ante

try now (sigma(n)-phi(n))/(n+phi(n))

Peter

fractions 1 and 2 so far

? for(n=1,10^8,if(Mod(sigma(n)-eulerphi(n),n+eulerphi(n))==0,print(n," ",(sigma(n)-eulerphi(n))/(n+eulerphi(n))," ",omega(n)," ",bigomega(n)," ",factor(n))))
1 0 0 0 matrix(0,2)
10 1 2 2 [2, 1; 5, 1]
44 1 2 3 [2, 2; 11, 1]
60 2 3 4 [2, 2; 3, 1; 5, 1]
168 2 3 5 [2, 3; 3, 1; 7, 1]
184 1 2 4 [2, 3; 23, 1]
752 1 2 5 [2, 4; 47, 1]
1530 2 4 5 [2, 1; 3, 2; 5, 1; 17, 1]
3672 2 3 7 [2, 3; 3, 3; 17, 1]
3796 1 3 4 [2, 2; 13, 1; 73, 1]
12224 1 2 7 [2, 6; 191, 1]

hm

Ante

there are some "almost-twin" solutions

Peter

15:44

almost twin ?

Ante

yes, close to each other, relatively

and much of solutions for this case

Peter

yes :

? for(n=1,10^8,if(Mod(sigma(n)-eulerphi(n),n+eulerphi(n))==0,print(n," ",(sigma(n)-eulerphi(n))/(n+eulerphi(n))," ",omega(n)," ",bigomega(n)," ",factor(n))))
1 0 0 0 matrix(0,2)
10 1 2 2 [2, 1; 5, 1]
44 1 2 3 [2, 2; 11, 1]
60 2 3 4 [2, 2; 3, 1; 5, 1]
168 2 3 5 [2, 3; 3, 1; 7, 1]
184 1 2 4 [2, 3; 23, 1]
752 1 2 5 [2, 4; 47, 1]
1530 2 4 5 [2, 1; 3, 2; 5, 1; 17, 1]
3672 2 3 7 [2, 3; 3, 3; 17, 1]
3796 1 3 4 [2, 2; 13, 1; 73, 1]
12224 1 2 7 [2, 6; 191, 1]

And this although sigma(n)-eulerphi(n) is much smaller than sigma(n) !

Ante

try now (sigma(n)-n)/(n+phi(n))

Peter

OK, this seems harder !

? for(n=1,10^8,if(Mod(sigma(n)-n,n+eulerphi(n))==0,print(n," ",(sigma(n)-n)/(n+eulerphi(n))," ",omega(n)," ",bigomega(n)," ",factor(n))))1 0 0 0 matrix(0,2)
12 1 2 3 [2, 2; 3, 1]
42 1 3 3 [2, 1; 3, 1; 7, 1]
1242 1 3 5 [2, 1; 3, 3; 23, 1]
6137440 1 4 8 [2, 5; 5, 1; 89, 1; 431, 1]

11045760 2 5 11 [2, 7; 3, 1; 5, 1; 11, 1; 523, 1]

maybe, we concentrate on this !

Look it up in OEIS , fun fact : 12,42 and 1242 are the first 3 solutions !

Ante

well, you should take a look at this:

for(n=1,10^8,if(Mod(sigma(n)+n,eulerphi(n))==0,print(n," ",(sigma(n)+n)/(eulerphi(n))," ",omega(n)," ",bigomega(n)," ",factor(n))))

(17:53) gp > for(n=1,10^13,if(Mod(sigma(n)+n,eulerphi(n))==0,print(n," ",(sigma(n)+n)/(eulerphi(n))," ",omega(n)," ",bigomega(n)," ",factor(n))))
1 2 0 0 matrix(0,2)
2 5 1 1 Mat([2, 1])
6 9 2 2 [2, 1; 3, 1]
10 7 2 2 [2, 1; 5, 1]
12 10 2 3 [2, 2; 3, 1]
28 7 2 3 [2, 2; 7, 1]
76 6 2 3 [2, 2; 19, 1]
120 15 3 5 [2, 3; 3, 1; 5, 1]
312 12 3 5 [2, 3; 3, 1; 13, 1]
588 13 3 5 [2, 2; 3, 1; 7, 2]
672 14 3 7 [2, 5; 3, 1; 7, 1]
888 11 3 5 [2, 3; 3, 1; 37, 1]
1060 8 3 4 [2, 2; 5, 1; 53, 1]
1264 6 2 5 [2, 4; 79, 1]

Peter

15:57

quite many solutions

Ante

yes

Peter

and also high fractions

If this is not in OEIS; it is worth a closer look

Ante

it is in oeis

but only 59 terms

in oeis

Peter

Hard to find a useful sequence not being in OEIS :(

How many do we have at the moment ?

Ante

about 40-45

even more

maybe

Peter

16:01

Just look at the largest in OEIS, and when you have beaten it

Ante

how to find non-primes for which this holds:

for(n=2,1000,if(Mod(sigma(n)+n,n-eulerphi(n))==0,print(n," ",(sigma(n)+n)/(n-eulerphi(n))," ",omega(n)," ",bigomega(n)," ",factor(n))))

n-eulerphi(n) is not interesting when n is prime

maybe that holds only for primes!

@Peter

Peter

16:51

command is "forcomposite"

? forcomposite(n=2,10^5,if(Mod(sigma(n)+n,n-eulerphi(n))==0,print(n," ",(sigma(n)+n)/(n-eulerphi(n))," ",omega(n)," ",bigomega(n)," ",factor(n))))
12 5 2 3 [2, 2; 3, 1]
247 17 2 2 [13, 1; 19, 1]
261 7 2 3 [3, 2; 29, 1]
270 5 3 5 [2, 1; 3, 3; 5, 1]
1386 5 4 5 [2, 1; 3, 2; 7, 1; 11, 1]
1710 5 4 5 [2, 1; 3, 2; 5, 1; 19, 1]
1817 37 2 2 [23, 1; 79, 1]
2279 49 2 2 [43, 1; 53, 1]
3960 6 4 7 [2, 3; 3, 2; 5, 1; 11, 1]
4469 61 2 2 [41, 1; 109, 1]
6720 6 4 9 [2, 6; 3, 1; 5, 1; 7, 1]
9167 97 2 2 [89, 1; 103, 1]

Ante

some composites pass the test

Peter

There is a conjecture that phi(n) | n-1 only holds for primes

Ante

Lehmer´s

Peter

A counterexample must be a Carmichael number with many factors.

Ante

but can phi(n)|n hold?

yes it can

Peter

16:58

For example for powers of 2

seems that the only possible prime factors are 2 and 3.

Can we prove this ?

Ante

both directions?

Peter

First that there cannot be prime factors p>=5

If we have at least two odd prime factors, then the valuation with respect to 2 is larger for phi(n) than for n

What about 2^a * p^b with p >= 5 ?

Above is not true, unfortunately, I cannot delete it. I only considered the squarefree case.

So , we start with n = 2^a * 3^b

Then, phi(n) = 2^(a-1) * 2 * 3^(b-1) = 2^a * 3^(b-1) | n , if a >= 1 and b >= 1

Ante

now converse

not like that

suppose that n=2^a*3^b*w and show w=1

Peter

17:15

phi(n) = 2^(a-1) * 2 * 3^(b-1) * phi(w) , if gcd(w,6)=1 and a,b>=1

hence we get phi(w) | w

but phi(w) is even for w>2 and w is odd

Ante

now suppose w=2^c * 3^d * r and use infinite descent, and done

or like that

Peter

Aren't we already done ? At least with the case a,b >= 1 ?

Ante

i think yes

Peter

Now, next b = 0

n = 2^a * w , gcd(w,6) = 1

phi(n) = 2^(a-1) * phi(w)

Hence phi(w) | 2w

A moment, above we do not have phi(w) | w , but phi(w) | 3w ...

but 3w is odd as well, so this case remains valid.

but what about phi(w) | 2w ?

Ante

i think that can be more easily proven with Euler´s product formula

all of that

Peter

17:30

we have n / phi(n) = p1 / (p1-1) * ... * pn/(pn-1) and if pn >=5 , this cannot be an integer.

Ante

yes

Peter

That's it, you were right !

Ante

yes

Peter

A power of 3 (not being 1) does not satisfy the property

So, necessary and sufficient is that 2 appears and 3 can also appear.

Ante

yes

Peter

17:32

Nice !

Ante

we can now dabble about n|sigma(n)

Peter

the multi-perfect numbers.

Ante

yes

:D

Peter

k = 2 is completely clasified for the even numbers, and odd numbers are not known

Ante

yes

since there are none, but we do not have a proof

Peter

17:36

If I am informed right, it is also conjectured that no odd examples exist for larger k.

But I am not sure.

OEIS probably has the entries upto a high limit ...

If I remember right, another conjecture is that there is a k-perfect number for every k >= 2

Ante

yes, and none of the odd k-perfects

they are all conjectured to be even

Peter

What is the search limit in OEIS ?

Ante

not sure

Peter

OK, I look it up ...

Hm, I did not find the list of all numbers, only for k = 2 , 3 , ...

Isn't that list in OEIS ? This would be strange !

Ante

Multiply perfect number

In mathematics, a multiply perfect number (also called multiperfect number or pluperfect number) is a generalization of a perfect number. For a given natural number k, a number n is called k-perfect (or k-fold perfect) if and only if the sum of all positive divisors of n (the divisor function, σ(n)) is equal to kn; a number is thus perfect if and only if it is 2-perfect. A number that is k-perfect for a certain k is called a multiply perfect number. As of 2014, k-perfect numbers are known for each value of k up to 11.It can be proven that: For a given prime number p, if n is p-perfect and p does...

Peter

17:46

But this does not summarize all known cases.

Some examples are "numerical monsters"

So , it might be worth to calculate the first examples.

Ante

for k=3?

Peter

Are the smallest examples known to be the smallest ? Or only the smallest known ?

Most will have k = 3 anyway.

? for(n=2,10^9,s=sigma(n)/n;if(denominator(s)==1,print(n," ",s," ",factor(n))))
6 2 [2, 1; 3, 1]
28 2 [2, 2; 7, 1]
120 3 [2, 3; 3, 1; 5, 1]
496 2 [2, 4; 31, 1]
672 3 [2, 5; 3, 1; 7, 1]
8128 2 [2, 6; 127, 1]
30240 4 [2, 5; 3, 3; 5, 1; 7, 1]
32760 4 [2, 3; 3, 2; 5, 1; 7, 1; 13, 1]
523776 3 [2, 9; 3, 1; 11, 1; 31, 1]
2178540 4 [2, 2; 3, 2; 5, 1; 7, 2; 13, 1; 19, 1]

23569920 4 [2, 9; 3, 3; 5, 1; 11, 1; 31, 1]
33550336 2 [2, 12; 8191, 1]
45532800 4 [2, 7; 3, 3; 5, 2; 17, 1; 31, 1]

this should be in OEIS !?

@Ante

Ante

oeis.org/…

oeis.org/A007691/b007691.txt

Peter

Are these only the known or do we know that in that range there are no more ?

Ante

most probably no more in that ranges

Peter

17:57

but this is not proven, right ?

Ante

well, it is computed

Peter

Surely not with brute force !

Ante

ah, you think it is done with some shortcuts

Peter

We cannot check every number upto this level ! Not the best computers can do that. But there are surely strong heuristics and restrictions.

Ante

i do not know, there are some so-called supercomputers and parallel computing

Peter

18:01

We also know that there are no perfect odd numbers upto 10^1500 , but this range has not been computer-checked, of course.

The numbers here have several hundred digits !

10^18 , maybe can be done with brute force.

Perhaps even 10^21, but 10^100, infeasible.

Ante

can you check is w(n)=p_{n+1}p_{n+2}+p_{n+2}p_{n}+p_{n+1}p_{n} "often" prime?

Peter

So, 3 consecutive primes a<b<c ?

Ante

yes

Peter

Is it ab + ac + bc , then ?

Ante

yes

Peter

18:08

the first is already prime ...

Ante

and second is

Peter

a moment ...

? while(c<1000,[a,b,c]=[b,c,nextprime(c+1)];if(ispseudoprime(a*b+a*c+b*c)==1,print([a,b,c,a*b+a*c+b*c])))
[3, 5, 7, 71]
[5, 7, 11, 167]
[7, 11, 13, 311]
[17, 19, 23, 1151]
[29, 31, 37, 3119]
[37, 41, 43, 4871]
[41, 43, 47, 5711]
[43, 47, 53, 6791]
[67, 71, 73, 14831]
[83, 89, 97, 24071]
[103, 107, 109, 33911]
[137, 139, 149, 60167]
[157, 163, 167, 79031]
[179, 181, 191, 101159]
[181, 191, 193, 106367]
[193, 197, 199, 115631]
[227, 229, 233, 158231]
[277, 281, 283, 235751]
[283, 293, 307, 259751]

in fact many primes !

Ante

very much

Peter

nice prime generator !

Let us count them !

Ante

thanks

Peter

18:13

? [a,b,c]=primes(3);q=1;while(c<5000,[a,b,c]=[b,c,nextprime(c+1)];if(ispseudoprime(a*b+a*c+b*c)==1,q=q+1;print([q,a,b,c,a*b+a*c+b*c])))
[2, 3, 5, 7, 71]
[3, 5, 7, 11, 167]
[4, 7, 11, 13, 311]
[5, 17, 19, 23, 1151]
[6, 29, 31, 37, 3119]
[7, 37, 41, 43, 4871]
[8, 41, 43, 47, 5711]
[9, 43, 47, 53, 6791]
[10, 67, 71, 73, 14831]
[11, 83, 89, 97, 24071]
[12, 103, 107, 109, 33911]
[13, 137, 139, 149, 60167]
[14, 157, 163, 167, 79031]
[15, 179, 181, 191, 101159]
[16, 181, 191, 193, 106367]
[17, 193, 197, 199, 115631]

119 primes !

Ante

yes, very much for so a trivial sequence

Peter

? [a,b,c]=primes(3);q=1;while(c<10^7,[a,b,c]=[b,c,nextprime(c+1)];if(ispseudoprime(a*b+a*c+b*c)==1,q=q+1));print(q)
56312
?

? [a,b,c]=primes(3);q=1;while(c<10^8,[a,b,c]=[b,c,nextprime(c+1)];if(ispseudoprime(a*b+a*c+b*c)==1,q=q+1));print(q)
418784
?

Ante

you can try also ab+bc+ac+a+b+c+1 to compare results

Peter

First of all, I have an explanation why the chance to get a prime is good. SInce (a,b,c) are pairwise coprime, every prime dividing a+b , a+c or b+c , cannot divide the sum.

? [a,b,c]=primes(3);q=1;while(c<10^8,[a,b,c]=[b,c,nextprime(c+1)];if(ispseudoprime(a*b+a*c+b*c+a+b+c+1)==1,q=q+1));print(q)
633973
?

This is even better !

Ante

yes

Peter

18:21

But here, I have no quick explanation.

Ante

it is better by about 50 percent

which is much

Peter

In fact, a big difference. Let us look at 10^9

A good question for MSE and MO. Why is this generator superior ?

Ante

i wouldn´t ask it on MSE

Peter

OK, ask it on MO

10^9 will take a while.

Ante

i can wait for the procedure to finish

Peter

18:26

I have not the result for either generator yet.

Ante

not a problem

Peter

? [a,b,c]=primes(3);q=1;while(c<10^9,[a,b,c]=[b,c,nextprime(c+1)];if(ispseudoprime(a*b+a*c+b*c+a+b+c+1)==1,q=q+1));print(q)
4944793
?

Ante

that´s a large increase since primes on average get rarer

Peter

yes. but only with about log(n)

Ante

we didn´t try the simplest ab+a+b+1

with two variables

no, that is vene

even

so ab+a+b

Peter

18:33

One after the other ...

Ante

ok

Peter

You switch faster to a new idea than Enzo Creti :)

Ante

well, i did not chat with Enzo, but yes, i have much ideas :)

Peter

not bad, but perhaps note those ideas and present them later, that I can keep up.

Ante

ah, i write rarer and rarer, you´ll remember what´s most important, i guess, at least some of it

Peter

18:36

? [a,b,c]=primes(3);q=1;while(c<10^9,[a,b,c]=[b,c,nextprime(c+1)];if(ispseudoprime(a*b+a*c+b*c)==1,q=q+1));print(q)
3237073
?

The same generator is again a clear winner !

Why is it better than the other ??

Ante

yes, again about 50 percent

try now ab+a+b

i think it will be stunning

or not

:P

Peter

19:03

running

Peter

19:23

? [a,b]=primes(2);q=1;while(b<10^9,[a,b]=[b,nextprime(b+1)];if(ispseudoprime(a*b+a+b)==1,q=q+1));print(q)
3119137
?

OK, I will think about all this. Good night.

Ante

bye

Ante

19:37

Masterphile.

Transcript for

$Mathematics$ Hilbert's hotel