Search found 27 matches

by castrate
Thu May 27, 2021 3:26 am
Forum: News, Suggestions, and FAQ
Topic: Tag-Based Organisation
Replies: 10
Views: 1868

Re: Tag-Based Organisation

It works again today. Thank you euler! :D
by castrate
Wed May 26, 2021 12:16 pm
Forum: News, Suggestions, and FAQ
Topic: Tag-Based Organisation
Replies: 10
Views: 1868

Re: Tag-Based Organisation

I had enabled Full Tags, and it'd been working for several days. However, the tags disappeared in problem pages today. What's more, when I typed in some frequently used tags like combinatorics or polynomial and clicked search, I didn't get results, but received a message reading "Removed 1 unre...
by castrate
Thu Mar 11, 2021 8:51 am
Forum: Number Theory
Topic: Calculating modular inverses of p mod $2^p$
Replies: 2
Views: 1063

Calculating modular inverses of p mod $2^p$

Let p an odd prime . We want to calculate $I(p)=p^{-1}\mod 2^p$. If we use EXGCD, it takes $O(\log_22^p)=O(p)$ time, which is not efficient enough. Some small values are 3, 13, 55, 931, 3781, 61681, 248347, 4011943, 259179061...... It seems that $I(p)$ is slightly smaller than $2^{p-1}$, but I didn'...
by castrate
Fri Feb 26, 2021 3:43 am
Forum: Clarifications on Project Euler Problems
Topic: Problem 688
Replies: 9
Views: 4163

Re: Problem 688

Hmm...Seems that I'm stuck. I tried sending PM to several administrators, but with no replies for over three months. So could someone help confirm the following results: S(10^6)=***xxxxxxx*** S(10^8)=***xxxxxxxxxxx*** S(10^10)=***xxxxxxxxxxxxxxx*** S(10^12)=***xxxxxxxxxxxxxxxxxxx*** EDIT digits remo...
by castrate
Thu Jan 21, 2021 9:52 am
Forum: Discrete Mathematics
Topic: Counting constrained squarefree numbers
Replies: 4
Views: 2158

Re: Counting constrained squarefree numbers

It seems that the formula above only holds when d is prime. For example, take d=6 and n=100, the formula yields $S_6(100)=11-2=9$, but actually $S_6(100)=5$. In fact, for squarefree $d=p_1 p_2$, the formula should be $S_{p_1 p_2}(n)=S(\lfloor\frac{n}{p_1 p_2}\rfloor)-S_{p_1}(\lfloor\frac{n}{p_1 p_2}...
by castrate
Thu Jan 21, 2021 1:12 am
Forum: Discrete Mathematics
Topic: Counting constrained squarefree numbers
Replies: 4
Views: 2158

Counting constrained squarefree numbers

As is known to all, the numbers of squarefree numbers below N can be computed in $O(\sqrt{N})$ time. Now we consider numbers which are both squarefree and NOT divisible by 3 and 5. For instance, there are 20 these numbers below 50, namely 1,2,7,11,13,14,17,19,22,23,26,29,31,34,37,38,41,43,46,47. So ...
by castrate
Sat Jan 02, 2021 9:58 am
Forum: Clarifications on Project Euler Problems
Topic: Problem 170
Replies: 5
Views: 3285

Re: Problem 170

Solved the problem, and the answer to leading zeroes appears to be No.
by castrate
Sat Jan 02, 2021 4:23 am
Forum: Clarifications on Project Euler Problems
Topic: Problem 170
Replies: 5
Views: 3285

Re: Problem 170

78*12645=986310
78*093=7254
So is 9863107254 a valid answer?
by castrate
Fri Jan 01, 2021 7:38 am
Forum: Discrete Mathematics
Topic: How to list all powerful numbers below N in $O(\sqrt{N})$time?
Replies: 1
Views: 592

How to list all powerful numbers below N in $O(\sqrt{N})$time?

Powerful numbers: A positive integer n is powerful if $p^2$ is a divisor of n for every prime factor p in n. From OEIS we know that the number of powerful numbers below N is about $2.1732\sqrt{N}=O(\sqrt{N})$ In fact I do have an algorithm to do so, but some technical issue beats me. The outline of ...
by castrate
Sun Dec 27, 2020 1:57 am
Forum: Discrete Mathematics
Topic: How to compute a two-variable recurrence function C(n,n) in O(n) time?
Replies: 2
Views: 680

How to compute a two-variable recurrence function C(n,n) in O(n) time?

Suppose we have a two-variable recurrence relation: $C(n,k)=C(n-1,k)+C(n,k-1)$ where boundary values such as $C(n,0)$ and $C(0,k)$ are given. Our target is to find $C(n,n)$. A simple DP algorithm could solve it, but in $O(n^2)$ time, which is not capable of large values of n ($10^7$ or higher). So i...
by castrate
Sat Sep 12, 2020 9:03 am
Forum: Clarifications on Project Euler Problems
Topic: Problem 641
Replies: 6
Views: 4400

Re: Problem 641

I got 69 for n=$10^8$, but the answer for $10^{36}$ was rejected. Can I PM someone for some higher results?
Edit:Solved the problem.
by castrate
Fri Sep 11, 2020 5:00 am
Forum: Number Theory
Topic: How to enumerate/count the numbers of a particular form below N in an efficient way?
Replies: 10
Views: 3584

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

My algorithm for {1,1,1,...,1} takes roughly O(N). By saying "efficient" here I mean to enumerate numbers of that form without brute force. In other words, an $O(\sqrt[\min(L)]N)$ implementation is efficient enough for me. (Of course, your $O(\sqrt[\max(L)]N)$ approach is much better)
by castrate
Sat Sep 05, 2020 3:59 am
Forum: Number Theory
Topic: How to enumerate/count the numbers of a particular form below N in an efficient way?
Replies: 10
Views: 3584

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.
by castrate
Fri Sep 04, 2020 1:16 pm
Forum: Number Theory
Topic: How to enumerate/count the numbers of a particular form below N in an efficient way?
Replies: 10
Views: 3584

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

Sorry, I don't fully understand your method. Is your $f(k)$, $g(\lfloor \dfrac n k \rfloor )$ equivalent to C(..., k) and C(..., $\lfloor \dfrac n k \rfloor$) as I described above?
by castrate
Fri Sep 04, 2020 4:16 am
Forum: Number Theory
Topic: How to enumerate/count the numbers of a particular form below N in an efficient way?
Replies: 10
Views: 3584

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

Thanks for your advice, but how may Dirichlet convolution work in this problem? I'm still new to that concept and its applications.
by castrate
Thu Sep 03, 2020 2:13 pm
Forum: Number Theory
Topic: How to enumerate/count the numbers of a particular form below N in an efficient way?
Replies: 10
Views: 3584

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

For a sorted array of integers L={$a_1,a_2,...,a_k$}(Eg. L=[3,3,2,2,1]), consider numbers n which can be factored in the form: $n=p_1^{a_1}p_2^{a_2}...p_k^{a_k}$, where $p_1, p_2,..., p_k$ are distinct primes . Let E(L, N) be the enumerating function of all numbers n, not exceeding N, which has the ...
by castrate
Mon Aug 31, 2020 12:12 pm
Forum: Number
Topic: Identity involving $\sigma(i·j)$
Replies: 3
Views: 1608

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

I found the formula on wolframalpha and solved problem 439 on yesterday evening. Thank you all the same. :D
by castrate
Sat Aug 29, 2020 2:23 am
Forum: Number
Topic: Identity involving $\sigma(i·j)$
Replies: 3
Views: 1608

Identity involving $\sigma(i·j)$

As far as I know, there is an identity involving d(i·j), where d(n) denotes the number of divisors of n: $d(i·j)=\sum_{x|i}\sum_{y|j}[gcd(x,y)=1]$ where [...]=1 if the condition holds, otherwise 0. However, when I was looking for similar identities involving $\sigma(i·j)$ in the form of $\sigma(i·j)...
by castrate
Tue Aug 25, 2020 6:11 am
Forum: Clarifications on Project Euler Problems
Topic: Problem 272
Replies: 15
Views: 12513

Re: Problem 272

I think I'm on the (seemingly)correct way, but the answer was wrong, even not the same with the "correct wrong" answer. Could you please check: Is the smallest number satisfying C(n)=242 <snipped>? And is the smallest number satisfying C(n)=242 and not divisible by 9 <snipped>? Edit: Solve...
by castrate
Fri Aug 21, 2020 1:28 pm
Forum: Number
Topic: Unit cube roots in number theory
Replies: 2
Views: 1792

Unit cube roots in number theory

I was trying to solve some particular PE problem these days. It is easy to verify that for any prime power p^k(except 2), there exist two solutions to the equation x^2=1(mod p^k), namely 1 and p^k-1. However, when dealing with the equation x^3=1(mod p^k), the result appeared to differ. For some prim...