insuring convergence of an algorithm (solving a set of equations)
pamela fluente
equations:
c(m) * x(m) = c(z+1) - y(m) where: m=1,2,...,z
where the (2 * z + 1) unknowns are: z, x(m), y(m). All natural
numbers.
c(m) is a sequence of pre-assigned, increasing, natural constants.
I need just 1 solution. I can probably proceed iteratively in the
search.
I'd like to find some preliminary test or fairly general conditions so
that, based on the data at hand,
i can know in advance if i will ever find 1 solution (and not engage
in an infinite loop). Ideas ?
Pam
Torsten
What about
z arbitrary,
x(m)=1
y(m)=c(z+1)-c(m) (1<=m<=z)
??
Best wishes
Torsten.
pamela fluente
wrote:
Thanks Torsten,
yes you are right!
I forgot to specify a constraint. Let me correct the formulation.
Please add:
y(m) is comprised between 1 and c(m)-1
Pam
Richard Harter
Either I am being dense, or you need to clarify your problem
statement. You have added the constraint
y(m) is comprised between 1 and c(m)-1
but that is not enough. As it stands you have z equations in 2*z+1
unknowns, where z is one of the unknowns. This is a massively
underdetermined system. Moreover there is no statement at all of what
it means to solve for z! From what you have given us there is a large
family of simple solutions, e.g.,
y(m) = random value satisfying 1 < y(m) < c(m)-1
x(m) = (c(z+1)-y(m))/c(m)
Now I doubt that this is what you are after but it satisfies what you
have given. It would be helpful if you could give a more complete
problem formulation using a more conventional presentation. Thus, so
far, we have:
Given a sequence of increasing constants c(i), i = 1... and, for
any given z, a sequence of equations
c(i)*x(i) = c(z+1) - y(i), i=1...z
subject to the constraint 1 < y(i) < c(i)-1
That is not much; clearly you have additional constraints and
conditions in mind, including conditions on the choice of z.
Torsten
>
> - Zitierten Text anzeigen -
A further constraint you did not notice was that
the x(i) and y(i) have to be natural numbers ...
Best wishes
Torsten.
pamela fluente
> On Fri, 25 Feb 2011 01:28:11 -0800 (PST), pamela fluente
>
> have given. It would be helpful if you could give a more complete
> problem formulation using a more conventional presentation. Thus, so
> far, we have:
>
> Given a sequence of increasing constants c(i), i = 1... and, for
> any given z, a sequence of equations
>
> c(i)*x(i) = c(z+1) - y(i), i=1...z
>
Thanks a lot Richard,
one of the reason i find so useful asking question is that
even by simply trying to ask the correct question i am forced to
understand better the problem.
Yes one feature here is that the number of equation is an unknown.
What this means is that, while one iterates, if a solution
does not exist for z equations, we consider (z+1) of them
(by adding another one).
So z would actually be the smallest z where the system finally
has 1 solution.
[ The constraint is: 1 <= y(i) <= c(i)-1 (extreme included) ]
The values:
y(m) = random value satisfying 1 < y(m) < c(m)-1
x(m) = (c(z+1)-y(m))/c(m)
may not be a solution [ if (c(z+1)-y(m))/c(m)
is not integer ] as x(m) must be an integer
(all constants/unknowns here are natural numbers,
where i mean positive integer).
Pam
Patricia Shanahan
> On 25 Feb, 17:13, c...@tiac.net (Richard Harter) wrote:
>> On Fri, 25 Feb 2011 01:28:11 -0800 (PST), pamela fluente
>>
>> Now I doubt that this is what you are after but it satisfies what you
>> have given. It would be helpful if you could give a more complete
>> problem formulation using a more conventional presentation. Thus, so
>> far, we have:
>>
>> Given a sequence of increasing constants c(i), i = 1... and, for
>> any given z, a sequence of equations
>>
>> c(i)*x(i) = c(z+1) - y(i), i=1...z
>>
>
> Thanks a lot Richard,
>
> one of the reason i find so useful asking question is that
> even by simply trying to ask the correct question i am forced to
> understand better the problem.
>
> Yes one feature here is that the number of equation is an unknown.
>
> What this means is that, while one iterates, if a solution
> does not exist for z equations, we consider (z+1) of them
> (by adding another one).
If a solution does not exist for z equations then any system formed by
adding another equation will also have no solutions. To transition from
no solution to having a solution you would have to remove at least one
equation.
Maybe you mean "If there are multiple solutions for z equations, we
consider (z+1) of them.".
What do you do if z equations have multiple solutions, and (z+1) have
none? Or does the form of your equations make that case impossible?
Patricia
Richard Harter
wrote:
>pamela fluente wrote:
>> On 25 Feb, 17:13, c...@tiac.net (Richard Harter) wrote:
>>> On Fri, 25 Feb 2011 01:28:11 -0800 (PST), pamela fluente
>>>
>>> Now I doubt that this is what you are after but it satisfies what you
>>> have given. It would be helpful if you could give a more complete
>>> problem formulation using a more conventional presentation. Thus, so
>>> far, we have:
>>>
>>> Given a sequence of increasing constants c(i), i = 1... and, for
>>> any given z, a sequence of equations
>>>
>>> c(i)*x(i) = c(z+1) - y(i), i=1...z
>>>
>>
>> Thanks a lot Richard,
>>
>> one of the reason i find so useful asking question is that
>> even by simply trying to ask the correct question i am forced to
>> understand better the problem.
>>
>> Yes one feature here is that the number of equation is an unknown.
>>
>> What this means is that, while one iterates, if a solution
>> does not exist for z equations, we consider (z+1) of them
>> (by adding another one).
>
>If a solution does not exist for z equations then any system formed by
>adding another equation will also have no solutions. To transition from
>no solution to having a solution you would have to remove at least one
>equation.
But that isn't what she is doing. When she iterates she changes all
of the previous equations and adds a new one. The right hand side
changes because of the c(z+1) term.
pamela fluente
> But that isn't what she is doing. When she iterates she changes all
> of the previous equations and adds a new one. The right hand side
> changes because of the c(z+1) term.
>
Yes, in fact a new "iteration" is done in the hope that, with the new
value
c(z+1), a solution exists.
Here the problem is not that i have too many solutions
(underdetermination), as it may seem at first sight,
it's quite the opposite: that i may have to make thousand (or millions
iterations) before finding 1 match.
I was hoping in a preliminary check or a general condition to avoid an
infinite loop.
-Pam
Richard Harter
<pamela...@libero.it> wrote:
>On 25 Feb, 17:13, c...@tiac.net (Richard Harter) wrote:
[snip]
>Thanks a lot Richard,
>
>one of the reason i find so useful asking question is that
>even by simply trying to ask the correct question i am forced to
>understand better the problem.
>
>Yes one feature here is that the number of equation is an unknown.
>
>What this means is that, while one iterates, if a solution
>does not exist for z equations, we consider (z+1) of them
>(by adding another one).
>So z would actually be the smallest z where the system finally
>has 1 solution.
My apologies for not catching the natural numbers qualifier. I assume
that "natural constants" are actually a sequence of pre-defined
positive integers. If I recall my thoughts correctly, I misunderstood
"natural numbers" as being real numbers. My bad. None-the-less it
would been clearer (to me, at least) if you had said positive integers
instead.
That said, I suspect there are some constraints on the values of c(z)
that haven't been mentioned yet. An obvious one is that all c(m) less
than z cannot be divisors of c(z) - otherwise there are no solutions.
Incidentally is correct that the constraint on y(m) is 1<y(m)<c(m)-1
rather than 1<=y(m)<c(m)-1?
pamela fluente
>
> My apologies for not catching the natural numbers qualifier. I assume
> that "natural constants" are actually a sequence of pre-defined
> positive integers. If I recall my thoughts correctly, I misunderstood
> "natural numbers" as being real numbers. My bad. None-the-less it
> would been clearer (to me, at least) if you had said positive integers
> instead.
>
> That said, I suspect there are some constraints on the values of c(z)
> that haven't been mentioned yet. An obvious one is that all c(m) less
> than z cannot be divisors of c(z) - otherwise there are no solutions.
>
> Incidentally is correct that the constraint on y(m) is 1<y(m)<c(m)-1
> rather than 1<=y(m)<c(m)-1?
Thanks Richard, absolutely no need to apologize. English is not my
first language
and it often happens that i am not clear: so my bad. Anyway
interacting with native speakers
is a good exercise and source of improvement.
> all c(m) less than z cannot be divisors of c(z)
Your observation is very acute.
Yes, we can assume that as a "trivial" case, or else there are no
solutions.
As to the constraint, probably it would not matter, but i am assuming
for now 1 <= y(m) <= c(m)-1 [is this important?]
-Pam
Richard Harter
<pamela...@libero.it> wrote:
>On 25 Feb, 21:21, c...@tiac.net (Richard Harter) wrote:
>>
>> My apologies for not catching the natural numbers qualifier. =A0I assume
>> that "natural constants" are actually a sequence of pre-defined
>> positive integers. =A0If I recall my thoughts correctly, I misunderstood
>> "natural numbers" as being real numbers. =A0My bad. =A0None-the-less it
>> would been clearer (to me, at least) if you had said positive integers
>> instead.
>>
>> That said, I suspect there are some constraints on the values of c(z)
>> that haven't been mentioned yet. =A0An obvious one is that all c(m) less
>> than z cannot be divisors of c(z) - otherwise there are no solutions.
>>
>> Incidentally is correct that the constraint on y(m) is 1<y(m)<c(m)-1
>> rather than 1<=3Dy(m)<c(m)-1?
>
>Thanks Richard, absolutely no need to apologize. English is not my
>first language
>and it often happens that i am not clear: so my bad. Anyway
>interacting with native speakers
>is a good exercise and source of improvement.
>
>
>> all c(m) less than z cannot be divisors of c(z)
>
>Your observation is very acute.
>Yes, we can assume that as a "trivial" case, or else there are no
>solutions.
>
>As to the constraint, probably it would not matter, but i am assuming
>for now 1 <=3D y(m) <=3D c(m)-1 [is this important?]
Yes. If I haven't missed something else, there are solutions for any
c(z+1)such that it is not divisible by any c(m), m<z+1. Here is the
key point. Suppose that c(z) = q*c(m)+r. Then the equation
c(m)*x(m)=c(z+1)-y(m) is satisfied by by x(m)=q, y(m)=r. On the other
hand, if c(z+1)=0 mod(c(m)) then y(m)=0 mod(c(m)) contrary to the
constraint. If the constraint is 1<y(m)<c(m)-1 then we get a similar
result with a further restriction.
I hope that this is what you are looking for and that I have not
missed something in the statement.
pamela fluente
Very interesting. I am still digesting it :-)
Can we ensure 1 solution with 1 <= y(m) <= c(m)-1,
and the additional constraint: y(m) <> c(m)-2 (<> i mean "different
from").
What would be the argument which ensures that by iterating
i will find the solution for sure in this latter case.
-Pam
Tim Little
> I need to write a program to solve a (variable-size) set of z
> equations:
>
> c(m) * x(m) = c(z+1) - y(m) where: m=1,2,...,z
>
> where the (2 * z + 1) unknowns are: z, x(m), y(m). All natural
> numbers. c(m) is a sequence of pre-assigned, increasing, natural
> constants.
It appears trivial: let z be any natural number and for all m, let
x(m) = 1 and y(m) = c(z+1) - c(m). Are you sure there aren't a lot of
other constraints you aren't telling?
This does appear to be a common pattern with your questions: the one
you initially post has trivial answers, but then over the course of
multiple rounds of elaboration it turns out that all of the previous
posts are irrelevant due to you failing to state the full problem.
--
Tim
Tim Little
This requires all c(m) to not divide c(z+1) but otherwise is trivial.
Find the first such z. Set x(m) and y(m) for each equation to the
quotient and remainder of c(z+1) / c(m).
No doubt there will be more conditions ...
--
Tim
Tim Little
> for now 1 <= y(m) <= c(m)-1 [is this important?]
Yes, very important. If it were 1 < y(m) < c(m)-1, then there would
be much tighter constraints on c(z+1).
--
Tim
Tim Little
> additional constraint: y(m) <> c(m)-2 (<> i mean "different from").
(As expected, additional constraints start popping up)
The latter condition has no bearing on reducing multiple solutions.
The first constraint already rules out multiple solutions for given z,
the second merely eliminates some z's from having any solutions at
all.
--
Tim
Richard Harter
<pamela...@libero.it> wrote:
>On 25 Feb, 22:05, c...@tiac.net (Richard Harter) wrote:
>> On Fri, 25 Feb 2011 12:49:10 -0800 (PST), pamela fluente
>>
>>
>>
>>
>>
>>
>>
>>
>>
>> <pamelaflue...@libero.it> wrote:
>> >On 25 Feb, 21:21, c...@tiac.net (Richard Harter) wrote:
>>
>> >> My apologies for not catching the natural numbers qualifier. =3DA0I as=
>sume
>> >> that "natural constants" are actually a sequence of pre-defined
>> >> positive integers. =3DA0If I recall my thoughts correctly, I misunders=
>tood
>> >> "natural numbers" as being real numbers. =3DA0My bad. =3DA0None-the-le=
>ss it
>> >> would been clearer (to me, at least) if you had said positive integers
>> >> instead.
>>
>> >> That said, I suspect there are some constraints on the values of c(z)
>> >> that haven't been mentioned yet. =3DA0An obvious one is that all c(m) =
>less
>> >> than z cannot be divisors of c(z) - otherwise there are no solutions.
>>
>> >> Incidentally is correct that the constraint on y(m) is 1<y(m)<c(m)-1
>> >> rather than 1<=3D3Dy(m)<c(m)-1?
>>
>> >Thanks Richard, absolutely no need to apologize. English is not my
>> >first language
>> >and it often happens that i am not clear: so my bad. Anyway
>> >interacting with native speakers
>> >is a good exercise and source of improvement.
>>
>> >> all c(m) less than z cannot be divisors of c(z)
>>
>> >Your observation is very acute.
>> >Yes, we can assume that as a "trivial" case, or else there are no
>> >solutions.
>>
>> >As to the constraint, probably it would not matter, but i am assuming
>> >for now =A01 <=3D3D y(m) <=3D3D c(m)-1 =A0 =A0[is this important?]
>>
>> Yes. =A0If I haven't missed something else, there are solutions for any
>> c(z+1)such that it is not divisible by any c(m), m<z+1. =A0Here is the
>> key point. =A0Suppose that c(z) =3D q*c(m)+r. =A0Then the equation
>> c(m)*x(m)=3Dc(z+1)-y(m) is satisfied by by x(m)=3Dq, y(m)=3Dr. =A0On the =
>other
>> hand, if c(z+1)=3D0 mod(c(m)) then y(m)=3D0 mod(c(m)) contrary to the
>> constraint. =A0If the constraint is 1<y(m)<c(m)-1 then we get a similar
>> result with a further restriction.
>>
>> I hope that this is what you are looking for and that I have not
>> missed something in the statement.
>
>Very interesting. I am still digesting it :-)
>
>Can we ensure 1 solution with 1 <=3D y(m) <=3D c(m)-1,
>and the additional constraint: y(m) <> c(m)-2 (<> i mean "different
>from").
>
>What would be the argument which ensures that by iterating
>i will find the solution for sure in this latter case.
for (z=1;z<max_z;z++) {
failed = m;
for (m=1;m<=z;m++) {
r = c(z+1)%c(m);
if (r==0) break;
if (r==c(m)-2) break;
failed--;
}
if (failed!=0) continue;
printf("solution found for z = %d\n",z);
break;
}
What this fragment of C code says is: Outer loop over z. Inner loop
over m. Within the inner loop compute q and r, the quotient and
remainder of c(z+1)/c(m). If all remainders are acceptable, you have
found a solution. The x and y arrays are:
x(m)=c(z+1)/c(m)
y(m)=c(z+1)%c(m)
The cost of finding a solution is O(z^2).
pamela fluente
> On Fri, 25 Feb 2011 13:19:08 -0800 (PST), pamela fluente
>
>
>
>
>
>
>
>
>
That is very interesting. But how does it ensure the existence of 1
solution ?
Or, what could be a condition to ensure the existence (under the
latest assumptions
you have correctly stated in the program) ?
Pam
pamela fluente
Thanks Tim,
There should be no more conditions. Richard's final formulation seems
a correct
description of my question.
What i wish to explore is when a solution is guaranteed to exists
and i will not loop forever. I am under the impression that
contributors
are taking for granted that 1 solution will always exists.
I may be missing something obvious that already ensure the solution to
always exists (?) for any sequence,
and therefore i was looking for a condition which would ensure the
existence of 1 solution.
(In practical terms, when Richard's program will not loop forever ? )
-Pam
Richard Harter
<pamela...@libero.it> wrote:
>On 26 Feb, 03:45, c...@tiac.net (Richard Harter) wrote:
[
>> What this fragment of C code says is: Outer loop over z. Inner loop
>> over m. Within the inner loop compute q and r, the quotient and
>> remainder of c(z+1)/c(m). =A0If all remainders are acceptable, you have
>> found a solution. The x and y arrays are:
>>
>> x(m)=c(z+1)/c(m)
>> y(m)=c(z+1)%c(m)
>>
>> The cost of finding a solution is O(z^2).
>
>That is very interesting. But how does it ensure the existence of 1
>solution ?
>
>Or, what could be a condition to ensure the existence (under the
>latest assumptions
>you have correctly stated in the program) ?
>
Formally, there exists an integer z such that for all m, 1<=m<=z,
c(z+1)mod(c(m)) is not equal to 0 or c(m)-2.
I don't suppose that is much help to you, but it is the necessary and
sufficient condition to ensure the existence. The problem is that
there is no guarantee for an arbitrary sequence c(z) z=1,...
To do what you want you need to supply us with more information about
this sequence.
>Pam
pamela fluente
I was thinking about a generic sequence and a generic condition.
Anyway to fix ideas, we could take this sequence:
Take an initial value x (at random > 100) and then generate the c's
with the following procedure:
c(1) = x
c(2) = c(1) + 3
c(3) = c(1) * c(2) + 4
...
c(m) = c(1) * ... * c(m-1) + (m+1).
(Would it converge to 1 solution for any x ?)
-Pam
Tim Little
> What i wish to explore is when a solution is guaranteed to exists
> and i will not loop forever.
In a certain sense, sequences where no solution ever exists are
"special", having density 0. Of course there are still infinitely
many such sequences. Uncountably infinite, even.
The only way to determine whether a sequence allows solutions is to
test all its terms. If the sequence is generated by some finite
algorithm, it may be possible to deduce from a description of the
algorithm (or it might not).
--
Tim
pamela fluente
> On 2011-02-26, pamela fluente <pamelaflue...@libero.it> wrote:
>
> > What i wish to explore is when a solution is guaranteed to exists
> > and i will not loop forever.
>
> In a certain sense, sequences where no solution ever exists are
> "special", having density 0.
This is actually a very interesting statement, what's the reasoning
behind ?
Actually, i think the most familiar and simplest sequence we might
think about could be the following one.
Let p(i) be the sequence of primes. Take an initial value r (any r >=
1000), and then define:
c(1) = p(h)
c(2) = p(h + 1)
...
c(m) = p(h + m-1)
can anyone prove that i will have *at least* 1 solution, for *at
least* one integer h >= r ? ;-))
-Pam
> Tim
Tim Little
> On 27 Feb, 10:10, Tim Little <t...@little-possums.net> wrote:
>> In a certain sense, sequences where no solution ever exists are
>> "special", having density 0.
>
> This is actually a very interesting statement, what's the reasoning
> behind ?
For a given initial finite sequence, there is a well-defined density
of next sequence values that yield no solution. Then you can define a
density product of finitely many "next" terms, and prove that as the
number of terms increases, it is bounded above by a sequence
converging to zero. The only exception is sequences starting with
c(1) = 1, for which no solution can ever exist.
> Actually, i think the most familiar and simplest sequence we might
> think about could be the following one.
> Let p(i) be the sequence of primes. Take an initial value r (any r >=
> 1000), and then define:
>
> c(1) = p(h)
> c(2) = p(h + 1)
> ...
> c(m) = p(h + m-1)
>
> can anyone prove that i will have *at least* 1 solution, for *at
> least* one integer h >= r ? ;-))
Is m here a variable, or fixed in advance? Is it the same thing as z
from the previous problem description?
--
Tim
pamela fluente
m is just an "enumerator".
c(m) = p(h + m-1) indicates the m-th term of the sequence of the c's
(in this case, the (h+m+1)-th prime).
In the previous posts, viewing the problem a growing set of z
equations,
z was also indicating the unknown which expresses the number of
necessary equations
to get 1 solution, as well as the z-th term of the sequence of the
c's.
-Pam
Tim Little
> m is just an "enumerator".
>
> c(m) = p(h + m-1) indicates the m-th term of the sequence of the c's
> (in this case, the (h+m+1)-th prime).
Ah okay. In that case z=1 will provide a solution for any h, with
x(1) = 1 and y(1) = p(h+1) - p(h). The condition 1 < y < p(h)
always holds by Bertrand's Postulate, and y(1) =/= p(h) - 2 because
y(1) is even and p(h) is odd.
This does seem a fairly trivial solution, though.
--
Tim
pamela fluente
Thanks Tim. Beautiful argument!
Actually as you rightly point out, the case of greater interest is for
z larger than a threshold.
Would it possible to extend a similar argument to the case z > k (k
any positive integer) or is it an impossible task ?
-Pam
Tim Little
> Would it possible to extend a similar argument to the case z > k (k
> any positive integer) or is it an impossible task ?
Since all the coefficients are prime, c(z+1) is obviously not a
multiple of any of them.
The remaining constraint was y =/= c(m)-2. That may be unsatisfied as
it is possible that c(z+1) = -2 mod c(m) for some m, but it becomes
less common for larger primes and there are plenty of prime candidates
c(z+1) for which it never holds.
I can't prove that there are infinitely many, but I did find examples
greater than 10^9.
--
Tim
pamela fluente
Thanks a lot, very nice results indeed Tim.
(Let me know in case, in future, some argument comes up in your mind.)
I think that the Bertrand postulate you mentioned is pretty useful.
-Pam
pamela fluente
> On 2011-03-02, pamela fluente <pamelaflue...@libero.it> wrote:
>
> I can't prove that there are infinitely many, but I did find examples
> greater than 10^9.
It would be incredibly good if given a solution at z, we could at
least
say what is the count s, where z + s is another solution. It's pretty
weird this
problem is so elusive that it's even so hard just to count the
numbers
to the next occurrence. After all, the remainders form a cyclically
ordered sequence
and it seems strange we can't "keep track" of them.
>
> --
> Tim
Tim Little
> It would be incredibly good if given a solution at z, we could at
> least say what is the count s, where z + s is another solution.
For your family of sequences, usually s=1.
> It's pretty weird this problem is so elusive that it's even so hard
> just to count the numbers to the next occurrence. After all, the
> remainders form a cyclically ordered sequence and it seems strange
> we can't "keep track" of them.
It's not elusive at all, it's just vaguely stated. I expect I could
write a program that tells which z's give solutions almost as fast as
the sequence values can stream in through the Ethernet port of my
computer.
The only "elusiveness" is that you're talking about an infinite family
of sequences, and speculating about common properties of their
collective solutions.
--
Tim
pamela fluente
> On 2011-03-05, pamela fluente <pamelaflue...@libero.it> wrote:
>
> > It would be incredibly good if given a solution at z, we could at
> > least say what is the count s, where z + s is another solution.
>
> For your family of sequences, usually s=1.
>
> > It's pretty weird this problem is so elusive that it's even so hard
> > just to count the numbers to the next occurrence. After all, the
> > remainders form a cyclically ordered sequence and it seems strange
> > we can't "keep track" of them.
>
> It's not elusive at all, it's just vaguely stated. I expect I could
> write a program that tells which z's give solutions almost as fast as
> the sequence values can stream in through the Ethernet port of my
> computer.
For simplicity, let's take the version r=h=1, so the c's are just the
plain and simple sequence of primes 2 3 5 ...
Let z > 2 be any integer which satisfies the system:
c(m) * x(m) = c(z+1) - y(m)
1 <= y(m) <= c(m)-1, y(m) <> c(m)-2
for all m= 1,2,3..., z
Can we really say immediately (i mean without going through each one
of the values following z)
for each z which is the next (z + s) also satisfying the system ?
Or can we jump directly from one solution to the next one ?
[ What seems strangely elusive to me is determining s = F(z) ]
-Pam
> Tim
Tim Little
> of the values following z) for each z which is the next (z + s) also
> satisfying the system ?
No. But again, why would you expect to be able to predict which
values of a sequence give solutions without being permitted to look at
them?
> [ What seems strangely elusive to me is determining s = F(z) ]
I don't see anything strangely elusive about that at all. The problem
is just that artificial restriction you're setting of not being
permitted to look at the values of c.
--
Tim
pamela fluente
Well ok, even allowing looking at ALL the values up to c(z+1), z > 2,
I believe that it will not
give any advantage. I think you still will find very difficult to
compute (not necessarily with a
closed form formula, but at least with a converging algorithm) the s
(distance from next solution).
The reason why this seems a little strange to me is that anyway the
remainders, from a given solution
follow cyclically a precise (and simple) sequence. So the elusive part
i see is in the fact that, while from
c(z+1) one we can know perfectly each of these sequences (because we
know perfectly all the remainders at that point),
still it seems difficult or impossible to compute directly at what
distance the same condition would occur.
-Pam
Tim Little
> Well ok, even allowing looking at ALL the values up to c(z+1)
It's the values *after* c(z+1) that matter just as much as the ones
before. Why do you expect to be able to determine whether c(z+2),
c(z+3), and so on allow solutions without being permitted to know what
values they have?
--
Tim
pamela fluente
> On 2011-03-06, pamela fluente <pamelaflue...@libero.it> wrote:
>
> > Well ok, even allowing looking at ALL the values up to c(z+1)
>
> It's the values *after* c(z+1) that matter just as much as the ones
> before. Why do you expect to be able to determine whether c(z+2),
> c(z+3), and so on allow solutions without being permitted to know what
> values they have?
>
Given any prime p(n), we can know (by division) all the remainders of
the divisions by the preceding primes. Denote these remainders are:
r(1) ... r(n-1) respectively.
Now the next prime p(n+1) could also be found as p(n) + d
where the distance d is the smallest positive integer j such that:
( r(s) + j ) mod p(s) <> 0 for all s=1,...,n
or equivalently:
( remainder of (p(n)/u) + j ) mod u <> 0 for all u=2,3,..
[ so we don't really need to know the values of the primes p(1) ...
p(n-1) ].
So we have a formula (algorithm) for any next prime (which actually
does not require knowledge of previous primes), and further we know
such a prime exists (algorithm is guaranteed to converge). But, as
soon as we add just 1 simple additional condition on remainders, like
for instance:
( r(s) + j ) mod p(s) <> p(s)-2
then it seems to me we cannot assure that the next prime, satysfying
also the above, exists at all. And this seemed a little strange. isn't
it ?
-Pam
Tim Little
> So we have a formula (algorithm) for any next prime (which actually
> does not require knowledge of previous primes), and further we know
> such a prime exists
Yes, as originally shown by Euclid using a rather ingenious argument.
It was not always obvious that there is no limit to the primes, and
Euclid's argument is very "fragile": change the properties of the set
even slightly, and it ceases to be useful at all (even if the set is
in fact infinite).
> But, as soon as we add just 1 simple additional condition on
> remainders, like for instance:
> ( r(s) + j ) mod p(s) <> p(s)-2
>
> then it seems to me we cannot assure that the next prime, satysfying
> also the above, exists at all. And this seemed a little strange. isn't
> it ?
It seems very likely that infinitely many such primes exist. I merely
stated that I could not prove it, a statement to be taken in the
context that I devote only a limited amount of time to newsgroup posts.
Note that there are very many unsolved conjectures concerning
infinitude of various classes of primes. I see nothing strange in the
idea that another such class might or might not be infinite, and that
I might not know whether it is or not. Do you?
--
Tim
pamela fluente
:-)) well, "intuitively" i could bet anything that such a prime will
always
exist, as 1) a consequence of the infinity of primes And 2) due to the
fact that
such infiniteness together with remainders' periodicity (replicated"
patterns") will
certainty cause this condition to re-occur again and again. But
actually putting out a
rigorous argument for that is all another matter, and probably elusive
for most minds!
In particular, I think it's condition 2) which will cause any possible
condition of this type
(or even any multiple combination of similar conditions) to be
verified on infinite primes
(clearly "rarer and rarer").
The basic problem is probably to find a good "method" to "count"
within this context of simultaneous
cyclic patterns... the whole problem could be "reduced" to mere
"counting" the integers occurring
within the occurrence of the various conditions...
-Pam
pamela fluente
by absurd:
assume that for n > M no primes allows anymore the occurrence of that
simultaneous conditions
on remainders...
... then this would certainly contradict the "periodicity" of the
remainders
0101010101
0012012012
0001230123
...
(some argument clearly still missing here :-))
But much way nicer would be a "constructive" approach, where we could
actually "count"
up to the next occurrence.
[infinitude of primes would be just be the most obvious of many
remarkable consequences]
-Pam