2
votes
4answers
462 views

Numbers whose digits sum to 7

Let $S$ be the sequence of all positive integers whose decimal digits add to exactly 7, in increasing order: $$S = \langle7, 16, 25, \ldots, 70, 106, 115, 124, \ldots 160, 205, \ldots, 10230010, ...
3
votes
1answer
37 views

Total number of possible sub sequence with given condition

Given a sequence of two letters A and B find the total number of possible sub sequences where number of letter A is two times the number of letter B without ...
1
vote
0answers
22 views

number set with non-adjacent digits

I'm not sure such thing exists, or even if I'm asking for a valid thing, but I'll do my best describing it. At least the thing I want is similar to Gray code, so should be valid. So, I want to know ...
0
votes
0answers
102 views

Find all the subsequences which are arithmetic progression

Given a sequence is there a linear or sub-linear algorithm to find all the sub-sequences that are arithmetic progressions with a given D, where D is the consecutive difference between the elements ?
0
votes
0answers
38 views

Computational Streaming Model - longest decreasing subsequence

Question: Given a sequence of numbers from a stream of length $n$ (Streaming Model) for example: $(2, 6, 4, 7, 2, 8, 3, 1)$ Determine the longest decreasing subsequence (LDS) of length $k$ in that ...
8
votes
3answers
206 views

Finding 1000th 5-smooth number

A number is 5-smooth if its only prime factors are $2,3$ or $5$. Example: $$1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, \dots$$ Interesting thing is that as they become larger and larger, they are ...
0
votes
2answers
71 views

summation of ceil and floor function

I need a closed solution or a faster algorithm for calculating $$ \sum_{k=1}^{n-1} \left\lceil \frac{n}{k}-1 \right\rceil $$ and $$ \sum_{k=1}^{n-1} \left\lfloor \frac{n}{k} \right\rfloor $$ where $ ...
0
votes
1answer
32 views

Number of configurations in a constrained nested loops and configuration back from serial

Consider 4 counters looping the digits 0, 1, 2 to form the various "configurations", like in : ...
1
vote
0answers
36 views

Performance estimation of shellSort

I'm trying to make a performance estimation for shell-sort algorithm. And I fail in it. My formula: equals to where dz is outer while-loop, dy is middle for-loop, and dx is inner for-loop ...
1
vote
1answer
38 views

How many majority elements can there be in a sequence?

You are given a sequence $S$ of $n$ numbers. An element $x$ in $S$ is called a majority element if it occurs more than $n$/2 times in $S$. This question asks you to describe two algorithms that decide ...
0
votes
1answer
51 views

Catastrophic Cancellation

I need some informations about algorithms to solve the problem of Catastrophic Cancellation, or in general to calculate mean and variance of a data stream. For example about Donald Knuth's algorithm ...
1
vote
1answer
52 views

Check if a series can be made or not

Given an infinite geometric sequence $S=\{1, \frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \dots \}$. I need to tell whether for given fraction $p⁄q$, we can select an infinite geometric sequence $R$, such ...
1
vote
1answer
86 views

How do computers calculate the log of a value? [duplicate]

I'm not sure if this question belongs on StackOverflow or here (please let me know if the former, and i'll delete this and ask there), but I was wondering how the ...
1
vote
1answer
59 views

Finding Required Permutation

I have numbers from $1$..$n$. I want to find number of permutation from all $n!$ permutation where the numbers have following arrangement. $L$ $G$ $L$ $G$ $L$ or $G$ $L$ $G$ $L$ $G$. Where L means ...
1
vote
1answer
45 views

Can all real numbers be presented via a natural number and a sequence in the following way?

Is there (for each fixed base system with digits $0,1,\dots,m$) and then for each real number $r\in\mathbb R$, an integer $n\in\mathbb Z$ and a sequence $(a_i)_{i\in\mathbb{N}}$ with ...
0
votes
3answers
26 views

Check The Series

If the nth term of a series is given by $T(n)=T(n-1) + T(n-1) \times C$ where $C$ is a given constant and $T(1)=A$ and $n \ge 2$ . I need to tell whether its value will be greater than $G$ or not ...
0
votes
0answers
47 views

Find all $a_i$ such that $(x_{a_1} - x_{a_2} + x_{a_3}) +\ldots + x_{a_{3k}}$ min

Given $n$ numbers $x_1, x_2, \ldots,x_n \in \mathbb{Z}$ and an integer $k \le\frac n 3$. Find $a_i$ $(i = \overline{1,2,3,\dots,3k}),\ 0 < a_i < a_{i+1} \le n$ such that: $$M = (x_{a_1} - ...
1
vote
1answer
53 views

Making longest sequence

F(N) is defined as number of digits in a number N. EXAMPLE : F(123)=3 I want to make a consecutive integer sequence starting from number m (m, m + 1, ...). But to add a number n to my sequence its ...
0
votes
0answers
24 views

String satisfying the condition

Given $N$, $A_0$, $B_0$, $L_0$, $A_1$, $B_1$ and $L_1$, find a sequence S consisting only of characters '$0$' and '$1$'(a total of N characters) such that: The number of '$0$'s in any consecutive ...
3
votes
0answers
76 views

Find all distinct binary de Bruijn sequences

Messing around with numbers has lead me to the following problem, which I am struggling with. (No, not a homework question, just a problem I've thought up myself): A binary De Bruijn sequence of ...
2
votes
4answers
558 views

How to find a closed form solution to a recurrence of the following form?

I need to find the closed form solution to the following recurrence -: $ T(n) = 8*T(n/2) + 0.25*n^2$ with $T(1) = 1$ and $n=2^j$ and this is what I have tried so far but just can't seem to get a ...
1
vote
1answer
55 views

Using series to produce guess for algorithm analysis

I need to find the upper asymptotic bound for the recursion: $$ T(k) = 2T(k-1)+\frac{1}{k} $$ I was able to determine: The height of this tree is $k-1$. The cost of each level is ...
6
votes
5answers
279 views

Fibonacci-like sequence

Today I have to deal with something which reminds Fibonacci sequence. Let's say I have a certain number k, which is n-th number of certain sequence. This sequence however is created by recursive ...
0
votes
0answers
202 views

Number of Anti-Arithmetic sequences.

Original Problem Link. A permutation $p$ is called antiarithmetic if there is no subsequence of it forming an arithmetic progression of length bigger than $2$, i.e. there are no three indices ...
1
vote
4answers
178 views

How is “n+n/2+n/4…1” equal to “2n-1” using the formula for geometric series?

I never knew not having good knowledge of basic maths will be so crippling!! So please help me out this time. I'll be working on my maths from today on. I was discussing about complexity of an ...
1
vote
1answer
84 views

what if geometric sequence + geometric sequence

I wrote a program that basicly can find the formula of the sequence that created with any-degree equation. For example if you give my program that sequence: [1926, 2811, 833240, 28778265, 398155842, ...
0
votes
1answer
65 views

General term of this sequence

I wanted to know the General term or the function to generate this sequence I found on OEIS. It is the number of ways to express $2n+1$ as $p+2q$; where $p$ and $q$ can be odd prime number and even ...
2
votes
2answers
368 views

Convergence of a Recursive Sequence - An Example

Consider the sequence $\displaystyle x(k+1) = \frac{1}{2}\left(x(k) + \frac{a}{x(k)}\right)$ where $x(k)$ stands for the $k$th term of the sequence. What does this process converge to, and what is ...
7
votes
4answers
560 views

General McNugget problem

The classic McNugget problem states: Chicken McNuggets can be purchased in quantities of 6, 9, and 20 pieces. You can buy exactly 15 pieces by purchasing a 6 and a 9, but you can't buy exactly 10 ...
2
votes
1answer
613 views

How to calculate $ 1^k+2^k+3^k+\cdots+N^k $ with given values of $N$ and $k$? [duplicate]

Here $ 1<N<10^9$ and $0<k<50$ So we have to calculate it in order of $O(\log N)$.
4
votes
2answers
254 views

Sum of the series formula

I need to figure out the sum of the series as quickly as possible in a program given n and k: $$f(n,k)= ...
3
votes
8answers
4k views

Fastest Square Root Algorithm

What is the fastest algorithm for finding the square root of a number? I created one that can find the square root of "987654321" to 16 decimal places in just 20 iterations (I'm not ready to release ...
1
vote
1answer
131 views

How to convert a sequence of numbers in the formula?

I'm trying to understand different sorting algorithms and their BigO notation. Suppose, I'm using insertion sort and I have the worst case: 6 | 5 | 4 | 3 | 2 | 1 ...
1
vote
1answer
77 views

What kind of series / recursion is this?

I'm trying to find the explicit solution / sum of first n elements for the following sequence: d(2) = 2 d(n) = d(n/2) + n*log2(n) Can you help me to find out ...
2
votes
1answer
615 views

Finding common terms of two arithmetic sequences using Extended Euclidean algorithm

I have a problem which could be simplified as: there are two arithmetic sequences, a and b. Those can be written as a=a1+m*d1 b=b1+n*d2 I need to find the ...
12
votes
2answers
322 views

Prime one heap Nim

I have been working on an interesting problem my lecturer mentioned recently. Prime Nim is a variant of the Nim game where you have a single pile with an arbitrary number $n\in \Bbb N+\{0\}$ of ...
5
votes
2answers
395 views

Computing nth term of fibonacci-like sequence for large n

Sum up to nth term of fibonacci sequence for very large n can be calculated in O($\log n$) time using the following approach: $$A = \begin{bmatrix} 1&1 \\\\1&0\end{bmatrix}^n$$ ...
4
votes
1answer
198 views

Permute the values in each row in a matrix such that the columns sum to the same amount.

The general problem Given a matrix, I would like to permute the order of values in each row, so that all the columns of the matrix sums to the same value. A simple example For example, given: ...
0
votes
2answers
232 views

Formalizing the idea of “algorithm”

I have encountered several times, while doing mathematics, the following situation: We have a finite "sequence" $\left(a_{n}\right)_{n\in\left\{ 1,\ldots,p\right\} }$ of some objects that has the ...
2
votes
1answer
80 views

What is the value of this summation in Big O terms?

I am trying to do an analysis for the cost of n inserts into a hashtable datastructure and I have a factor like the one below: $$\sum_{i=0}^{\lfloor\lg {(n-1)}\rfloor} 2^i$$ What will be the Big O ...
2
votes
1answer
902 views

Induction proof of lower bound for $\sum \sqrt n$

I'm having some trouble proving the following statement using mathematical induction: $$\frac{1}{2}n^{\frac{3}{2}} \leq \sqrt{1} + \sqrt{2} + \sqrt{3} + \sqrt{4} + ... + \sqrt{n} ,\text{ (for ...
0
votes
2answers
67 views

Ordered subsets summation

Let $A$ and $B$ two finite ordered sets where $A\subseteq B$. How do I count the number of consecutive and non-consecutive ocurrences of $A$ in $B$? For instance, I have nine ocurrences of set ...
5
votes
3answers
121 views

Understanding this summation identity

I'm currently reading a book in which part of the solution to the problem involve this identity: $$\sum_{j=i+1}^{n}j = \sum_{j=1}^{n}j-\sum_{j=1}^{i}j$$ Which I cannot derive myself. The only thing ...
4
votes
4answers
719 views

Calculation of Bessel Functions

I want to calculate the Bessel function, given by $$J_\alpha (\beta) = \sum_{m=0}^{\infty}\frac{(-1)^m}{m!\Gamma(m+\alpha +1)} \left(\frac{\beta}{2}\right)^{2m}$$ I know there are some tables that ...
1
vote
1answer
40 views

Formula to scale a series that is being bent with a root / power.

I have a reference number, Rx, and a series of numbers, Sx[], to compare to it. Let's call the output Ox[]. I am using a simple square root to accelerate the apparent difference between the reference ...
-1
votes
3answers
2k views

Efficient algorithms for computing Digits Sums Numbers

Is there any efficient way to generate these numbers? The sequence OEIS A038367: Numbers $n$ with property that (product of digits of $n$) is divisible by (sum of digits of $n$). First few: ...
0
votes
1answer
386 views

Represent loop nests as multiple summations?

This may be trivial but I would appreciate if someone could point me in the right direction here.. I am trying to express the number of instances in a loop nest in a general form. As a mathematical ...
2
votes
1answer
61 views

Maximising the product of exponents, but minimising the product of the base raised to its respective exponent

Given the following sequences: let value = $(b_0^{p_0})(b_1^{p_1})\cdots(b_n^{p_n})$ let productOfExponents = $p_0 \cdot p_1 \cdots p_n$ Where $p_i\geq 0$ and $p_i$ an element of $\mathbb{N}$ for ...
2
votes
1answer
397 views

About Self Number, which is found by D. R. Kaprekar.

I'm trying to understand the algorithm to find self-number. But I don't know what does C, k, j, b is mean at this formula. What's that? How do I understand and what should I assign to solve them?
2
votes
1answer
109 views

What's the fastest way to find this sum of “like multiplications”?

Suppose that we have two sequences of $n$ naturals, which we'll call $a$ and $b$. We can denote the $k$th value in the sequence by the term $a_k$ and $b_k$ respectively. We can then define a like ...