Wall-Sun-Sun primes - Page 2

Gandolf · 2016-01-23, 09:33

Quote:

Originally Posted by CRGreathouse

The paper you cite was written, apparently, by two undergrads (sophomores, the paper says). It doesn't source the conjecture.

The Sun-Sun paper
http://matwbn.icm.edu.pl/ksiazki/aa/aa60/aa6046.pdf
doesn't make this conjecture. The Williams paper
http://www.sciencedirect.com/science...98122182900268
says that "Wall's problem is to find a p such that ...", and suggests the 1/p heuristic which suggests infinitely many exist.

Peng
http://arxiv.org/abs/1511.05645
though says that Wall conjectured (something equivalent to the nonexistence of these primes). I don't have a copy of Wall's paper at the moment, but if so then this should properly be called Wall's conjecture rather than W-S-S since the latter two do not join him.

Ah, thank you very much. I knew something wasn't consistent across the papers, because it was hard to relate the question to the conjecture.

Wall asked if u(p)=u(p^2) is always impossible, from what I've read. Semantically, it could imply existence, but I would assume the question would be this instead: Is u(p)=u(p^2) ever possible?

I do think Wall's conjecture was meant to imply a pattern of non-existence, yet open to the possibility of existence. Apparently, Wall's question is equivalent to, Is $F_{(p^2)}\mid F_{(F_{(u_{p^1})})}$ always impossible?

If an integer $m$ , has prime factorization, $p_{1}^{e_{1}}\cdot\ p_{2}^{e_{2}}...p_{n}^{e_{n}}$ then the "entry point"(index) of $m$ equals, $u_{m} = \operatorname{lcm}({ u_{p_{1}^{e_{1}}}, u_{p_{2}^{e_{2}}}, ... u_{p_{n}^{e_{n}}}})$ .

Consider $m=F_{(F_{(u_{p^1})})}$ , where the prime factorization is grouped into packets of $F_{(p^e)}$ , except for any product of primitive factors, which always have an entry point of $F_{(u_{p^1})}$ .

Suppose $p_{1}$ is a Fibonacci Wieferich prime, then $m=(F_{(p_{1}^2)}\ \cdot\ F_{(p_{2}^{e_{2}})}\ \cdot\ ...\ F_{(p_{n}^{e_{n}})}\ \cdot\ \prod{})=F_{(F_{(u_{p^1})})}$ .

The entry point of $m=F_{(F_{(u_{p^1})})}$ is always supposed to be $F_{(u_{p^1})}$ never $F_{(p*u_{p^1})}$ .

However in this case, $u_m=\operatorname{lcm}(p_{1}^{2},\ p_{2}^{e_{2}},\ ...\ p_{n}^{e_{n}},\ F_{(u_{p^1})})\ \neq F_{(u_{p^1})}=F_{(p*u_{p^1})}$ .

$F_{(p^2)}$ cannot divide $F_{(F_{(u_{p^1})})}$ , together with those other factors.

CRGreathouse · 2016-01-23, 18:29

Quote:

Originally Posted by Gandolf

Wall asked if u(p)=u(p^2) is always impossible, from what I've read. Semantically, it could imply existence, but I would assume the question would be this instead: Is u(p)=u(p^2) ever possible?

I do think Wall's conjecture was meant to imply a pattern of non-existence, yet open to the possibility of existence. Apparently, Wall's question is equivalent to, Is $F_{(p^2)}\mid F_{(F_{(u_{p^1})})}$ always impossible?

I'll have to get a copy of the paper to check if he posed it as an open question or if he made a conjecture.

Gandolf · 2016-01-23, 20:58

Quote:

Originally Posted by CRGreathouse

I'll have to get a copy of the paper to check if he posed it as an open question or if he made a conjecture.

Page 528 I think.

Quote:

Remark. The most perplexing problem we have met in this study concerns the hypothesis $k_{p^2}\text{ not equal to } k_{p}$ . We have run.... ....however cannot yet prove that $k_{p^2} = k_{p}$ is impossible. The question is closely related to... can a number x have the same order mod p and mod p^2?...; hence one might conjecture that equality may hold for some exceptional p.

Gandolf · 2016-01-27, 11:59

I wasn't able to obtain copyright permission to post the details here, but if anyone is interested in reading his original paper, free see here: http://www.jstor.org/stable/2309169?...n_tab_contents

The paper starts:

Quote:

This inquiry is concerned with determining the length of the period... The problem arose in connection with a method for generating random numbers, but it turned out to be unexpectedly intricate, and so quickly became of interest in its own right....
At least two questions remain unanswered... Remark 1, and 2.

Remark 2.
Theorems 6 and 7 furnish upper bounds for the function k(p), and we easily find cases where k(p) has these maximum values. On the other hand, we cannot find a nontrivial lower bound for k(p)...

If you read theorem 2, it shows the entry point relationship, which is stated more clearly(conveniently) in M. Renault's 1996 paper. http://webspace.ship.edu/msrenault/f.../FibThesis.pdf http://webspace.ship.edu/msrenault/fibonacci/fib.htm
Marc has not found any flaws in his theorem, nor in this application of it, relating to the proof. Although he is still looking at it closely.

Gandolf · 2016-01-30, 15:26

Let $F_{(u_{p^1})}$ , denote the least positive Fibonacci number divisible by the prime $p$ .
Let $F_{(u_{p^2})}$ , denote the least positive Fibonacci number divisible by $p^2$ .
Let $\prod_{1}^{n\ge 1}$ be a quotient of primitive(characteristic) prime factor(s), ie factors that have not occurred in any earlier Fibonacci numbers.
This may be represented below as an empty product of one, if the quotient divides $F_{(p^{e}_{1})},\ e>1$ .

${n \mid m}\ \text{iff}\ {F_{(n)}\mid F_{(m)}}\, n \ge 3$

$p^2 \mid F_{(u_{p^1})}\ \text{iff}\ F_{(p^2)} \mid F_{(F_{(u_{p^1})})}$
If an integer $i$ , has prime factorization, $p_{1}^{e_{1}}\cdot\ p_{2}^{e_{2}}...p_{n}^{e_{n}}$ then the entry point of $i$ equals, $u_{i} = \operatorname{lcm}[{ u_{(p_{1}^{e_{1}})}, u_{(p_{2}^{e_{2}})}, ...u_{(p_{n}^{e_{n}})}}]$ .

$\text{If}\ i=F_{(F_{(u_{p^1})})}\ \text{then, }\ F_{(p^2)} \not| F_{(F_{(u_{p^1})})}\text{ because } u_{F_{(F_{(u_{p^1})})}}\neq u_{F_{(F_{(u_{p^2})})}}$ .

An abstract example of a Fibonacci-Wieferich prime p, where $p_{1}=p,\ e_{1}\ge 2$ .
If $i=F_{(F_{(u_{p^1})})}=(F_{(p_{1}^2)}\ \cdot\ F_{(p_{2}^{e_{2}})}\ \cdot\ ...\ F_{(p_{n}^{e_{n}})}\ \cdot\ \prod{})$ then, can the entry point of $i$ still equal the same index, ie $u_{(F_{(F_{(u_{p^1})}}))}=F_{(u_{p^1})}$ ?
Answer: No.
Proof: ''This is based upon the observation that the entry point of the product of primitive prime factors, is supposed to be equal to the entry point of the product of non-primitive prime factors, ie Fibonacci numbers with unique factorization for indices, in this case.''

The factor, $j=(F_{(p_{1}^1)}\ \cdot\ F_{(p_{2}^{e_{2}})}\ \cdot\ ...\ F_{(p_{n}^{e_{n}})}\ \cdot\ \prod{})$ always has an entry point of, $u_j=\operatorname{lcm}[p_{1}^1,\ p_{2}^{e_{2}},\ ...\ p_{n}^{e_{n}},\ F_{(u_{p^1})}]=\operatorname{lcm}[p_{1}^1,\ p_{2}^{e_{2}},\ ...\ p_{n}^{e_{n}}]=F_{(u_{p^1})}$ .
While the factor $i$ has a later entry point, $u_i=\operatorname{lcm}[p_{1}^{2},\ p_{2}^{e_{2}},\ ...\ p_{n}^{e_{n}},\ F_{(u_{p^1})}]=\operatorname{lcm}[p_{1}^{2},\ p_{2}^{e_{2}},\ ...\ p_{n}^{e_{n}}]\neq F_{(u_{p^1})}=F_{(p\cdot u_{p^1})}$

$F_{(u_{p^1})}\neq F_{(u_{p^2})}$

$u_{(p^1)}\neq u_{(p^2)}$

$u_{(p^2)} = p\cdot u_{(p^1)}$

$p^{2}\not| F_{(u_{p^1})}$

Gandolf · 2016-02-21, 08:54

Charles, what is your opinion on the subject now?

Gandolf · 2016-09-24, 20:14

Quote:

Originally Posted by CRGreathouse

I'll have to get a copy of the paper to check if he posed it as an open question or if he made a conjecture.

Hey Charles, have you gotten a copy of the paper yet? What do you think, is it an open question or, did he make a conjecture in your opinion?

Do you think a counter-example, aka Wall-Sun-Sun prime will eventually be found with brute force?

CRGreathouse · 2016-09-25, 05:18

Quote:

Originally Posted by Gandolf

Hey Charles, have you gotten a copy of the paper yet? What do you think, is it an open question or, did he make a conjecture in your opinion?

I don't think I ever found a copy. I'm not comfortable guessing what he may have had in mind.

Quote:

Originally Posted by Gandolf

Do you think a counter-example, aka Wall-Sun-Sun prime will eventually be found with brute force?

It's not terribly likely. PrimeGrid has searched for one using lots of computer power without finding one. If by a massive effort they searched a thousand times as far, the heuristic chances they'd find one is around 8% if I recall properly. It's not terrible but not great either, and that would be a huge effort. It doesn't look like Moore's law can help us either. More math might, though -- I could imagine more properties being found which allowed a search (possibly non-exhaustive) much further.

Gandolf · 2016-09-25, 18:49

Quote:

Originally Posted by CRGreathouse

It's not terribly likely. PrimeGrid has searched for one using lots of computer power without finding one. If by a massive effort they searched a thousand times as far, the heuristic chances they'd find one is around 8% if I recall properly. It's not terrible but not great either, and that would be a huge effort. It doesn't look like Moore's law can help us either. More math might, though -- I could imagine more properties being found which allowed a search (possibly non-exhaustive) much further.

True, and Primegrid had the WSS bug. If I am not mistaken this invalidates a lot of the results, and they'd need to be re-checked. The exact heuristics are in question, from what I've read. Things have changed over the years, although one of the Sun brothers "apparently" contacted a Primegrid member, after that last false positive, and was confident that we would find a WSS soon. Honestly, I have not heard the same answer from any two professors. Seriously.

I agree that better math is needed. This problem is almost like "man versus machine".
A human seems the most likely to spit out the correct answer.

CRGreathouse · 2016-09-25, 23:29

Quote:

Originally Posted by Gandolf

I agree that better math is needed. This problem is almost like "man versus machine".
A human seems the most likely to spit out the correct answer.

I was thinking more "man and machine": a human develops methods that allow the search to become much more efficient, but computers are still needed to process what's left. Sort of like mapping the pseudoprimes to 2^64 a few years back.

chalsall · 2016-09-25, 23:46

Quote:

Originally Posted by CRGreathouse

I was thinking more "man and machine": a human develops methods that allow the search to become much more efficient, but computers are still needed to process what's left. Sort of like mapping the pseudoprimes to 2^64 a few years back.

No. What is going to happen is the AIs are going to take control.

Get used to it. We will be kind in our disposal of you.

2016-01-30, 15:26	#16
Gandolf Jan 2016 1E₁₆ Posts	Proof Let $F_{(u_{p^1})}$ , denote the least positive Fibonacci number divisible by the prime $p$ . Let $F_{(u_{p^2})}$ , denote the least positive Fibonacci number divisible by $p^2$ . Let $\prod_{1}^{n\ge 1}$ be a quotient of primitive(characteristic) prime factor(s), ie factors that have not occurred in any earlier Fibonacci numbers. This may be represented below as an empty product of one, if the quotient divides $F_{(p^{e}_{1})},\ e>1$ . ${n \mid m}\ \text{iff}\ {F_{(n)}\mid F_{(m)}}\, n \ge 3$ $p^2 \mid F_{(u_{p^1})}\ \text{iff}\ F_{(p^2)} \mid F_{(F_{(u_{p^1})})}$ If an integer $i$ , has prime factorization, $p_{1}^{e_{1}}\cdot\ p_{2}^{e_{2}}...p_{n}^{e_{n}}$ then the entry point of $i$ equals, $u_{i} = \operatorname{lcm}[{ u_{(p_{1}^{e_{1}})}, u_{(p_{2}^{e_{2}})}, ...u_{(p_{n}^{e_{n}})}}]$ . $\text{If}\ i=F_{(F_{(u_{p^1})})}\ \text{then, }\ F_{(p^2)} \not\| F_{(F_{(u_{p^1})})}\text{ because } u_{F_{(F_{(u_{p^1})})}}\neq u_{F_{(F_{(u_{p^2})})}}$ . An abstract example of a Fibonacci-Wieferich prime p, where $p_{1}=p,\ e_{1}\ge 2$ . If $i=F_{(F_{(u_{p^1})})}=(F_{(p_{1}^2)}\ \cdot\ F_{(p_{2}^{e_{2}})}\ \cdot\ ...\ F_{(p_{n}^{e_{n}})}\ \cdot\ \prod{})$ then, can the entry point of $i$ still equal the same index, ie $u_{(F_{(F_{(u_{p^1})}}))}=F_{(u_{p^1})}$ ? Answer: No. Proof: ''This is based upon the observation that the entry point of the product of primitive prime factors, is supposed to be equal to the entry point of the product of non-primitive prime factors, ie Fibonacci numbers with unique factorization for indices, in this case.'' The factor, $j=(F_{(p_{1}^1)}\ \cdot\ F_{(p_{2}^{e_{2}})}\ \cdot\ ...\ F_{(p_{n}^{e_{n}})}\ \cdot\ \prod{})$ always has an entry point of, $u_j=\operatorname{lcm}[p_{1}^1,\ p_{2}^{e_{2}},\ ...\ p_{n}^{e_{n}},\ F_{(u_{p^1})}]=\operatorname{lcm}[p_{1}^1,\ p_{2}^{e_{2}},\ ...\ p_{n}^{e_{n}}]=F_{(u_{p^1})}$ . While the factor $i$ has a later entry point, $u_i=\operatorname{lcm}[p_{1}^{2},\ p_{2}^{e_{2}},\ ...\ p_{n}^{e_{n}},\ F_{(u_{p^1})}]=\operatorname{lcm}[p_{1}^{2},\ p_{2}^{e_{2}},\ ...\ p_{n}^{e_{n}}]\neq F_{(u_{p^1})}=F_{(p\cdot u_{p^1})}$ $F_{(u_{p^1})}\neq F_{(u_{p^2})}$ $u_{(p^1)}\neq u_{(p^2)}$ $u_{(p^2)} = p\cdot u_{(p^1)}$ $p^{2}\not\| F_{(u_{p^1})}$

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
The Joys of Cracked.com: 5 Ways We Ruined the Occupy Wall Street Generation	Dubslow	Soap Box	17	2012-05-14 08:51
Wall Street Pundits are such Weenies	ewmayer	Soap Box	25	2009-06-17 23:07
Head, meet wall	fivemack	Factoring	13	2007-04-13 23:26
possible primes (real primes & poss.prime products)	troels munkner	Miscellaneous Math	4	2006-06-02 08:35
The Ladder Against The Wall	Numbers	Puzzles	27	2005-07-02 10:19

2016-02-21, 08:54	#17
Gandolf Jan 2016 2×3×5 Posts	Charles, what is your opinion on the subject now?