« first day (351 days earlier)      last day (110 days later) » 

10:32 AM
I'm not sure where I could pose a challenge to find best $f(n)$ so people will join in. $n\ge 5$ will never probably be proven optimal, but some lucky computations or out of the box analysis might give nice results.
(Given $n$ fixed digits and operations $(+,-,\times,\div)$, whats the highest $N\in\mathbb N$, such that all numbers $1\dots N$ can be built? $f(n)=N$)
$f(n)=1,3,10,52,\ge 333,\ge ?, \ge ?, \dots$
Previous best $f(5)=324$ was built like: pastebin.com/hhwW7FKK for example.
 
11:13 AM
According to factordb, no prime of the form $p^p+2$ with prime $p>3$ for $p\le 30\ 000$
 
11:37 AM
I have proven now $f(n)\ge 2^n-1,n\ge 1$ and $f(n)\ge 2^n+3, n\ge 3$, which is also another proof for $f(n)=1,3,10,\dots$ now, and the best lower bound I have.

Using digits $d=\{1,2,4,8,16,\dots,2^{n-1}\}$ this can be shown.
$2^n+2$ not $2^n+3$
 
 
7 hours later…
6:43 PM
@Vepir Actually if one uses the digits of $d$ additively it is equivalent to an n-bit system...
 
7:03 PM
@TheSimpliFire $d_i=2^{i-1}$ set i mentioned? How does equivalence with n-bit system affect this case?
 
I don't know, but I wonder if it is at all useful to make a base-2 representation. Division may cause a problem, however.
 
This case boils down to: "What is the smallest number not representable by combinations of $n$ consecutive power of $2$ using the basic four operations of $+,-\times,\div$?"
The answer is $f_d(n)+1$ by definition.

$f_d(n)=2^n-1$ for $n\ge1$ is the best bound. Then as you increase $n\ge k$ we get $f_d(n)=2^n-1+g(k)$ where $g(k)=0,0,3,11,45,533,\dots$

How to find $g(k)$?
(In terms of $n$?)
That is, I have that smallest number not representable by $d=\{1,2,4,8,\dots,2^{n-2},2^{n-1}\}$ is $f_d(n)+1$ where $f_d(n)=2^n-1+g(k)$.

The Main Question is: Can we find $d$ such that we can show $f_d(n)$ grows even faster than the above one for $\{1,2,4,8,\dots,2^{n-2},2^{n-1}\}$ ?

Regarding improving the lower bound on my newest problem.
 
7:24 PM
@TheSimpliFire You mentioned base, is it true that using digits $\lt b$ means we can represent some number $N$ using $\le (b+1)\log_b N$ digits, if only $+,\times$ are allowed?
If $b=2$, $3\log_2 N$ bound is given: https://arxiv.org/pdf/1310.2894.pdf and explained: " The upper bound can be obtained by writing $N$ in binary and finding a
representation using Horner’s algorithm."

So if we actually allow $\le b$ digits, we have $log_b N$ digits and that many bases, so the bound would be $2\log_b N$? https://en.wikipedia.org/wiki/Horner%27s_method @TheSimpliFire
 
Interesting question
 
Yes but this does not translate to $f(n)\ge b^{n/2}$ since we have a fixed set of digits $d$ sadly. This is only true if $b=2$ and $d={1}$ but then $b^{n/3}=2^{n/3}$.

I think.
 
Too much set theory in that paper :P
 
@TheSimpliFire Only the first page is important :P It presents the $3\log_2 N$ bound
Which is equivalent to $f(n)\ge 2^{N/3}$ in my problem.
I was wondering if it holds for more $b$, but direct translation back to my problem is not trivial since my "optimal $d$" is fixed.
fixed per case of $n$ - number of digits
 
@Vepir As an example we could try considering base 10 and see if the bound of $11\log N$ holds
 
7:38 PM
The problem is inverting the bound which is not trivial if $b\ne 2$.

For example, we can build $1=2-1$ using $1,2$ digits but adding onto $5$ and having now a set $1,2,5$ does NOT allow to rebuild $1$ since all digits must be used.
So keeping consecutive integers from $n-1$ digit case is not guaranteed. This is the issue.
The $d$ is fixed at $n$ digits and all need to be used.
Thats why I took $d_i=2^{i-1}$ digit sets since we can divide two largest to get the $n-1$ case and this allows to obtain bound $f(n)\ge2^n-1$ eventually.
Inductively.
$i=1,\dots,n$
This is not the issue if all digits are $1$'s also, on which they give bound $3\log_2 N\ge a(N)$ which can be translated to $f(n)\ge 2^{N/3}$ since multiplying two $1$'s reduces the case to $n-1$ and allows induction.
We need to inductively build digits $d_i$ so next set can achieve at least what previous one did.
Otherwise, it is hard to prove the next step is better when adding more digits.
For example we can add $d_0,d_0/2,d_0/2$ where $d_0$ can be anything since $d_0-d_0/2-d_0/2$ reduces us to case $n-3$. The comments discuss setting better bounds using similar construction (on my last question)
I'm not sure if you have the full context of the question or if this makes sense so sorry for clogging up the chat :P
 
@Vepir I'm just reading the progress every now and again so I might have missed a few things. I do have your original question but have only skimmed it
 
7:57 PM
The power of two digit set $d$ is optimal for $n=1,2,3$ but $n=4$ has $d=\{2,3,4,22\}$ being optimal (I conjecture strongly)
I'm not sure how to inductively relate this to previous or to extend to $n=5$.
If we could prove we can relate $n$ to $n-1$ and find a sequence formula for next digit $d_{n+1}$ to add onto $n+1$ case we would have $f(n)$ exactly but this seems hard.
Assuming $d$ is optimal.
In fact, I dont think this inductive argument will help find optimal sequence of digits to append to next case, maybe only improve lower bounds.
 

« first day (351 days earlier)      last day (110 days later) »