Project Euler

[Michael F. Stemper]

In problem 27 at Project Euler <https://projecteuler.net/problem=27>,
the challenge is to provide a quadratic expression that generates
primes.

In ordinary usage, a prime is positive. However, in algebraic number
theory, you can have primes over Z, which can be negative.

Does anybody know which usage is intended in this problem?

--
Michael F. Stemper
Nostalgia just ain't what it used to be.

[Mike Terry]

On 29/09/2022 22:37, Michael F. Stemper wrote:
> In problem 27 at Project Euler <https://projecteuler.net/problem=27>,
> the challenge is to provide a quadratic expression that generates
> primes.
>
> In ordinary usage, a prime is positive. However, in algebraic number
> theory, you can have primes over Z, which can be negative.
>
> Does anybody know which usage is intended in this problem?
>

It seems to me that the wording implies/suggests negative primes are ok.

The wording says:

n^2 + an + b must be prime for (a run of n starting at) n=0
|b| <= 1000
...

so by implication b < 0 is allowed, and for n=0, (n^2 + an + b) = b.

If primes had to be positive, why say |b| <= 1000, rather than 0 < b < 1000? That would just be
unnecessarily deceptive wording IMO. (That's not an iron-clad argument of course.)

Anyway, this looks like a trivial problem to just brute force (around 4 million cases to check),
whereas other projecteuler problems I've looked at involve some level of maths insight to achieve a
solution in a reasonable computation time. Perhaps I'm not seeing something! :)


Mike.

[Michael F. Stemper]

On 29/09/2022 17.54, Mike Terry wrote:
> On 29/09/2022 22:37, Michael F. Stemper wrote:
>> In problem 27 at Project Euler <https://projecteuler.net/problem=27>,
>> the challenge is to provide a quadratic expression that generates
>> primes.
>>
>> In ordinary usage, a prime is positive. However, in algebraic number
>> theory, you can have primes over Z, which can be negative.
>>
>> Does anybody know which usage is intended in this problem?
>>
>
> It seems to me that the wording implies/suggests negative primes are ok.
>
> The wording says:
>
>    n^2 + an + b  must be prime for (a run of n starting at) n=0
>    |b| <= 1000
>    ...
>
> so by implication b < 0 is allowed, and for n=0, (n^2 + an + b) = b.

I was going to use that fact to further constrain b to 2<=b<998. But,
then I remembered the idea of "primes over Z".

> If primes had to be positive, why say |b| <= 1000, rather than 0 < b < 1000?  That would just be unnecessarily deceptive wording IMO.

Well, I was thinking along those lines, but had the more
charitable interpretation of "loose wording". But, I guess
that I'll limit b to 1<|b|<998, which isn't much of a constraint.

> Anyway, this looks like a trivial problem to just brute force (around 4 million cases to check),

So far, I've only used brute force on Problem 20. Checking each
case does, of course, require evaluating the expression multiple
times. (How many, I don't know yet.)

> whereas other projecteuler problems I've looked at involve some
level of maths insight to achieve a solution in a reasonable computation time.

And I did Problem 25 without writing any program at all. My
approach to these has been to start off, not writing python,
but TeX. I apply as much math as I can, and use what I get to
design my code.

>  Perhaps I'm not seeing something! :)

My need for an elegant solution.

Thanks for the follow-up.

--
Michael F. Stemper
Psalm 82:3-4

[Mike Terry]

ok, I wrote the code to do a brute force search, and found that the maximum run of primes was the
same whether or not we included negative primes as valid. :)

There's a discussion thread on the site for the problem, and in there someone said they'd learned
that primes are considered to be only positive - but that's not really right, as you realise. In
the context of more general integral domains, primes/irreducibles are defined purely in terms of
their factoring properties, which makes -5 etc. primes in the ring of integers.

Anyway... I used to frequent this group a long time ago, but it died more or less. There is a
group sci.math, and there have been a couple of threads about some other project euler problems. So
probably you would get a better responses there... (I'm about to unsubscribe from this group.)

Regards,
Mike.

[Michael F. Stemper]

On 01/10/2022 08.15, Mike Terry wrote:
> On 30/09/2022 22:18, Michael F. Stemper wrote:
>> On 29/09/2022 17.54, Mike Terry wrote:
>>> On 29/09/2022 22:37, Michael F. Stemper wrote:
>>>> In problem 27 at Project Euler <https://projecteuler.net/problem=27>,
>>>> the challenge is to provide a quadratic expression that generates
>>>> primes.

>>>   Perhaps I'm not seeing something! :)
>>
>> My need for an elegant solution.
>>
>> Thanks for the follow-up.
>>
>
> ok, I wrote the code to do a brute force search, and found that the maximum run of primes was the same whether or not we included negative primes as valid.  :)
>
> There's a discussion thread on the site for the problem, and in there someone said they'd learned that primes are considered to be only positive - but that's not really right, as you realise.  In the context of more general integral domains, primes/irreducibles are defined purely in terms of their factoring properties, which makes -5 etc. primes in the ring of integers.
>
> Anyway...  I used to frequent this group a long time ago, but it died more or less.  There is a group sci.math, and there have been a couple of threads about some other project euler problems.  So probably you would get a better responses there...   (I'm about to unsubscribe from this group.)

There's actual discussion of math on sci.math? I'm amazed. I
used to be a regular there, but about five years back, it
became a wretched hive of scum and villainy, so I let it go.

Maybe I should in on it again.

--
Michael F. Stemper
Deuteronomy 10:18-19

[Mike Terry]

Yes it's full of cranks, and there's little "actual maths" being discussed. But... probably more
than is being discussed here! It's a shame, as this was a great group - posters here asked
questions and (mostly) genuinely wanted to learn the subject so it felt worthwhile to spend time
helping with answers.

For Sci.math I'd recommend heavy use of filtering - I find "ignore subthread" based on From: header
keeps it manageable, but there's little/no "serious" maths discussed - that seems to have all gone
to math stack exchange or mathoverflow.net. Sci.math very rarely goes beyond high-school level.

Mike.