A useful function. - Page 3

LaurV · 2018-03-02, 03:44

Quote:

Originally Posted by Batalov

Attachment deleted.

+1

JM Montolio A · 2018-03-03, 23:14

Hi, one question about the number of bits ONE of a number.
¿ Is some very know topic ? ¿ there is a PARIGP function for it ?
I think i find some beautiful property. Can be wrong, or can be old. I tell us.

Let n prime, with (n-1)=M(n)*S(n). And [2^M(n)]-1 = n*D.
Define f(n) as the number of bits ONE of any number n.
What i find is: if we compute the f(i*D) for all "i" odd less than n, starting at 1.
THEN and only if n is prime, there are S(n) sets of "i",
and for all i of any set, the f(i*D) is equal, and equal to the cardinality of their set.

I give 1 short example. n 23.
n 23, M 11, D 89, Dbit 4, s 2
n 23 i 1 iD 89 bits 4
n 23 i 3 iD 267 bits 4
n 23 i 5 iD 445 bits 7
n 23 i 7 iD 623 bits 7
n 23 i 9 iD 801 bits 4
n 23 i 11 iD 979 bits 7
n 23 i 13 iD 1157 bits 4
n 23 i 15 iD 1335 bits 7
n 23 i 17 iD 1513 bits 7
n 23 i 19 iD 1691 bits 7
n 23 i 21 iD 1869 bits 7
Two sets. (1,3,9,13),(5,7,11,15,17,19,21).
Cardinality. 4, 7. bits=f(iD)=cardinality.

¿ What is that property ?
JM M

CRGreathouse · 2018-03-04, 02:35

Quote:

Originally Posted by JM Montolio A

Hi, one question about the number of bits ONE of a number.
¿ Is some very know topic ? ¿ there is a PARIGP function for it ?

I think the function you're looking for is hammingweight (which I actually contributed).

JM Montolio A · 2018-03-07, 11:42

I suspect M(n) = znorder( Mod( 2,n) ).

M properties proof that Mersenne numbers are square free.

Properties of znorder must also proof it.

I think.

science_man_88 · 2018-03-07, 11:56

Quote:

Originally Posted by JM Montolio A

I suspect M(n) = znorder( Mod( 2,n) ).

M properties proof that Mersenne numbers are square free.

Properties of znorder must also proof it.

I think.

prove*

LaurV · 2018-03-08, 05:49

Quote:

Originally Posted by JM Montolio A

M properties proof that Mersenne numbers are square free.

no, it does not.... you still have to show that if p goes to q, then p^2 goes to pq, and that is not true, wieferich primes are the counterexample.

Dr Sardonicus · 2018-03-08, 14:29

The OP PM'd me a C program. It was so convoluted, with so many variables, I found it nearly impossible to relate the code to the comments describing what it was supposed to be doing.

However, what the code appeared to be doing was, starting with M = 0, and for a given odd number n, repeatedly incrementing M by 1, and for each M computing 2^M (mod n) by finding, via something like "Russian peasant multiplication," a number D such that

0 < 2^M - n*D < n.

It appeared that the process stopped when an M and D were found for which 2^M - n*D = 1, or if the computation of D caused an overflow.

If this is what the program is actually doing, it should stop when M is equal to the multiplicative order of 2 (mod n).

I can certainly think of faster ways to compute the multiplicative order of 2 (mod n), but I would be hard-pressed to find a slower way.

OP now on my ignore list...

2018-03-03, 23:14	#24
JM Montolio A Feb 2018 1100000₂ Posts	Question about the number of bits ONE of a number. Hi, one question about the number of bits ONE of a number. ¿ Is some very know topic ? ¿ there is a PARIGP function for it ? I think i find some beautiful property. Can be wrong, or can be old. I tell us. Let n prime, with (n-1)=M(n)S(n). And [2^M(n)]-1 = nD. Define f(n) as the number of bits ONE of any number n. What i find is: if we compute the f(iD) for all "i" odd less than n, starting at 1. THEN and only if n is prime, there are S(n) sets of "i", and for all i of any set, the f(iD) is equal, and equal to the cardinality of their set. I give 1 short example. n 23. n 23, M 11, D 89, Dbit 4, s 2 n 23 i 1 iD 89 bits 4 n 23 i 3 iD 267 bits 4 n 23 i 5 iD 445 bits 7 n 23 i 7 iD 623 bits 7 n 23 i 9 iD 801 bits 4 n 23 i 11 iD 979 bits 7 n 23 i 13 iD 1157 bits 4 n 23 i 15 iD 1335 bits 7 n 23 i 17 iD 1513 bits 7 n 23 i 19 iD 1691 bits 7 n 23 i 21 iD 1869 bits 7 Two sets. (1,3,9,13),(5,7,11,15,17,19,21). Cardinality. 4, 7. bits=f(iD)=cardinality. ¿ What is that property ? JM M

2018-03-07, 11:42	#26
JM Montolio A Feb 2018 1100000₂ Posts	I suspect M(n) = znorder( Mod( 2,n) ). M properties proof that Mersenne numbers are square free. Properties of znorder must also proof it. I think. Last fiddled with by JM Montolio A on 2018-03-07 at 11:44

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Fun with partition function	Batalov	And now for something completely different	24	2018-02-27 17:03
phi function	rula	Homework Help	3	2017-01-18 01:41
Gamma function	Calvin Culus	Analysis & Analytic Number Theory	6	2010-12-23 22:18
Solve for mod function	flouran	Miscellaneous Math	23	2009-01-04 20:03
Quick mod function ?	dsouza123	Math	16	2004-03-04 13:57

2018-03-08, 14:29	#29
Dr Sardonicus Feb 2017 Nowhere 2·5·433 Posts	The OP PM'd me a C program. It was so convoluted, with so many variables, I found it nearly impossible to relate the code to the comments describing what it was supposed to be doing. However, what the code appeared to be doing was, starting with M = 0, and for a given odd number n, repeatedly incrementing M by 1, and for each M computing 2^M (mod n) by finding, via something like "Russian peasant multiplication," a number D such that 0 < 2^M - nD < n. It appeared that the process stopped when an M and D were found for which 2^M - nD = 1, or if the computation of D caused an overflow. If this is what the program is actually doing, it should stop when M is equal to the multiplicative order of 2 (mod n). I can certainly think of faster ways to compute the multiplicative order of 2 (mod n), but I would be hard-pressed to find a slower way. OP now on my ignore list...