## Search found 53 matches

Wed Oct 21, 2020 1:01 pm
Forum: Clarifications on Project Euler Problems
Topic: Problem 371
Replies: 42
Views: 18814

### Re: Problem 371

hk wrote: Tue Oct 20, 2020 9:26 am That post of mine is really a long, long time ago.
But the problem under discussion is still a problem, and the solution which I'm proposing is (AFAICT) new.
Tue Oct 20, 2020 8:50 am
Forum: Clarifications on Project Euler Problems
Topic: Problem 371
Replies: 42
Views: 18814

### Re: Problem 371

I fear that explaining in considerable more detail makes an otherwise nice problem almost unreadable. But the nonsense about numberplates has already made an otherwise nice problem almost unintelligible. It would be better to ditch that entirely and write a problem statement which only gives the ni...
Tue Oct 13, 2020 11:57 am
Forum: News, Suggestions, and FAQ
Topic: Suggestion for new awards
Replies: 3
Views: 288

### Re: Suggestion for new awards

They currently cover 1-200, 201-300, 1-400. The obvious continuation would be 401-600, 1-800. If there's a desire to add awards, Conquering Difficulties looks like another that could be extended. Possibilities include the obvious "Solve at least N problems at all of the difficulty levels" for higher...
Thu Oct 08, 2020 7:29 am
Forum: Clarifications on Project Euler Problems
Topic: What kinda math should i know?
Replies: 1
Views: 539

### Re: What kinda math should i know?

"Elementary number theory" will help with an awful lot of them. "Enumerative combinatorics" is also a popular topic. It helps to be able to recognise a Markov process and know how to analyse it with linear algebra. There are plenty of probability questions, so you'll need to know what expectation is...
Mon Oct 05, 2020 7:45 pm
Forum: News, Suggestions, and FAQ
Topic: "You are the nth person to solve this problem"
Replies: 5
Views: 3471

### Re: "You are the nth person to solve this problem"

Adding extra data, like the position which it was solved to each member's profile, would not only add additional DB storage overhead, but it is not necessarily a fixed value and over time might begin to become inaccurate due to the reasons already mentioned. Yes, that would be a bad way of doing it...
Tue Sep 29, 2020 8:30 am
Forum: Recreational
Topic: big O notation of PE problems
Replies: 3
Views: 675

### Re: big O notation of PE problems

edit: Do you know of any problems < 100 where the time complexity can be easily calculated? I know of some where it can be upper-bounded, but giving the bounds would be a partial spoiler for the solution. (In fact, once you've done a couple of hundred problems the size of the input often gives you ...
Tue Sep 22, 2020 8:27 am
Forum: Recreational
Topic: big O notation of PE problems
Replies: 3
Views: 675

### Re: big O notation of PE problems

The subject of asymptotics confuses many people, and often needs careful statement to avoid confusing the rest. Big-O notation is a notation, that is to say, a representation. The representation is not the same as the thing it represents, which is the asymptotic behaviour of something. A statement t...
Sat Sep 19, 2020 11:55 pm
Forum: Clarifications on Project Euler Problems
Topic: Problem 710
Replies: 13
Views: 2474

### Re: Problem 710

I am partially happy to report that my spreadsheet grew to 822 permutations, so now I am only missing two! Sorry, not so. E.g. compare columns RY and ACN, which by my reckoning are both (7, 2, 2, 2, 7). Also, the reason people aren't looking at your spreadsheet might be because it's a nuisance to t...
Mon Sep 14, 2020 8:21 am
Forum: Number Theory
Topic: How to enumerate/count the numbers of a particular form below N in an efficient way?
Replies: 10
Views: 1383

### Re: How to enumerate/count the numbers of a particular form below N in an efficient way?

Maybe worth a quick note, then, that a basic sieve can enumerate all squarefree numbers, grouping them by number of prime factors, in $\tilde O(n)$ time.
Thu Sep 10, 2020 2:56 pm
Forum: Clarifications on Project Euler Problems
Topic: Problem 004
Replies: 85
Views: 21740

### Re: Problem 004

@Ontogenes, you're looking for a number which has two properties: (1) it's a palindrome; (2) it's a product of two 3-digit numbers. There are three basic approaches: (A) generate all numbers and test both properties; (B) generate all numbers having the first property and test whether they have the s...
Wed Sep 09, 2020 8:51 am
Forum: Number Theory
Topic: How to enumerate/count the numbers of a particular form below N in an efficient way?
Replies: 10
Views: 1383

### Re: How to enumerate/count the numbers of a particular form below N in an efficient way?

Actually, I'm now curious about: For trivial or specific cases, such as L={1,1,1,1} or L={2,1}, it is easy to come up with an efficient algorithm(I have a recursive algorithm for L={1,1,1,1}). My technique gives theoretical asymptotics of $O(N^{23/24})$ for $\{1,1,1,1\}$, which doesn't really seem p...
Mon Sep 07, 2020 5:44 pm
Forum: Number Theory
Topic: How to enumerate/count the numbers of a particular form below N in an efficient way?
Replies: 10
Views: 1383

### Re: How to enumerate/count the numbers of a particular form below N in an efficient way?

Got it, but can this implementation compute C(L,N) efficiently? For example, for the case C({5,5,3},$10^{18}$), we need an $O(N^{1/3})$ approach, and for the case C({7,7,5},$10^{30}$),we need an $O(N^{1/5})$ approach. I'm not quite sure why $O(\sqrt[\min(a_i)]{N})$ is the cutoff for "efficient". Lo...
Fri Sep 04, 2020 6:56 pm
Forum: Number Theory
Topic: How to enumerate/count the numbers of a particular form below N in an efficient way?
Replies: 10
Views: 1383

### Re: How to enumerate/count the numbers of a particular form below N in an efficient way?

No, they're indicator functions $I_L(n) = C(L, n) - C(L, n-1)$.
Fri Sep 04, 2020 8:08 am
Forum: Number Theory
Topic: How to enumerate/count the numbers of a particular form below N in an efficient way?
Replies: 10
Views: 1383

### Re: How to enumerate/count the numbers of a particular form below N in an efficient way?

The sums involved are of the form $\sum_{k=1}^N f(k)\, g(\lfloor\tfrac{n}{k}\rfloor)$ where $f,g$ are indicator functions for $E(?,N)$.
Thu Sep 03, 2020 11:12 pm
Forum: Number Theory
Topic: How to enumerate/count the numbers of a particular form below N in an efficient way?
Replies: 10
Views: 1383

### Re: How to enumerate/count the numbers of a particular form below N in an efficient way?

I think you are already familiar with inclusion-exclusion, fast evaluation of the prime counting function, and sums of Dirichlet convolutions. Just put them together...
Wed Sep 02, 2020 8:10 am
Forum: Number
Topic: Identity involving $\sigma(i·j)$
Replies: 3
Views: 631

### Re: Identity involving $\sigma(i·j)$

I think it's compatible with the aims and ethos of this site to say that it's easy to show that such an $F$ exists by strong induction: just take $\sigma(i\cdot j)=\sum_{x|i}\sum_{y|j}F(x,y)$ as defining $F(i, j)$. As to whether there's a more useful expression for it, one can use the inductive defi...
Fri Aug 28, 2020 11:57 am
Forum: Clarifications on Project Euler Problems
Topic: Problem 431
Replies: 10
Views: 4221

### Re: Problem 431

The problem statement says: We shall let the amount of space wasted in cubic metres be given by $V(x)$. If $x = 1.114785284$, which happens to have three squared decimal places, then the amount of space wasted, $V(1.114785284) \approx 36$. Given the range of possible solutions to this problem there ...
Sat Aug 22, 2020 1:06 am
Forum: Number
Topic: Unit cube roots in number theory
Replies: 2
Views: 849

### Re: Unit cube roots in number theory

Solutions to $x^3 = 1$ are roots of $x^3 - 1$ which factors as $(x-1)(x^2+x+1)$. For $p \neq 2$ you can complete the square as over the reals, giving $x = 2^{-1}(-1 \pm \sqrt{-3})$. Square roots modulo a prime can be computed by the Tonelli-Shanks algorithm. Solutions modulo a prime power can be obt...
Thu Aug 13, 2020 5:28 pm
Forum: News, Suggestions, and FAQ
Topic: Website Maintenance 30 July 2020
Replies: 35
Views: 4532

### Re: Website Maintenance 30 July 2020

Just as an impression without actual timing data, the wait for the green tick seems higher than usual today. I don't know whether this is related to the maintenance, but I thought I'd mention it.
Tue Aug 04, 2020 11:02 am
Forum: Programming languages
Topic: the Spartan way of C
Replies: 5
Views: 1076

### Re: the Spartan way of C

lucasart wrote: Tue Aug 04, 2020 5:47 am PS: C and C++ are completely different ball games. They shouldn't be lumped together. It's obvious that this groupping was made by mathematicians, not programmers.
Bear in mind that the grouping was made two decades ago, when C++ had diverged much less from C than it has now.