14
$\begingroup$

Suppose you start with number $1$ and at each step you can apply one of the functions $$\{2x+1, 3x, 3x+2, 3x+7\}$$ to it. Can you reach at every number of $8k+7$ form?

P.s What I already know :

  1. the same is not true for the $4k+3$ instead of $8k+7$, there is a counter example for that ( some number bigger than a thousand which I don't remember exactly)
  2. I could prove that there is a number $l$ such that all $2^lk+2^l-1$ are reachable
  3. There is computer aided proof to show all numbers like $128k+127$ can be reached

(from comment) I was playing with affine maps and their properties which I encountered this example and property which I verified by computer but can't prove it.

New contributor
Erfan Tavakoli is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
14
  • 1
    $\begingroup$ Welcome to MSE. Here's how to ask a good question. Follow these guidelines to get help in this forum. $\endgroup$
    – jjagmath
    May 12 at 10:26
  • 2
    $\begingroup$ @ErfanTavakoli This is exactly the kind of context you should add into the question : Something like "brute force shows that upto $k=10^6$ , every such number can be reached" and some background how this set emerged. By the way, I did not downvote since the question itself is interesting. $\endgroup$
    – Peter
    May 12 at 10:33
  • 1
    $\begingroup$ @ErfanTavakoli For example your comment "I was playing with affine maps and their properties which I encountered this example and property which I verified by computer but can't prove it" it useful as context of the problem. Also you should add your work in the problem. $\endgroup$
    – Event Horizon
    May 12 at 10:33
  • 2
    $\begingroup$ @ErfanTavakoli You're expected to share your work on the problem, something that shows that you put some thought on the problem before asking for help. Your questions will be better received in this forum if the post show some effort, no just posting the question. $\endgroup$
    – jjagmath
    May 12 at 11:59
  • 1
    $\begingroup$ The question is much better now (+1) , but if you work out how you proved your partial results someone might be able to fill up the gaps. Moreover, we can approve your partial results. $\endgroup$
    – Peter
    May 13 at 9:52

1 Answer 1

Reset to default
2
$\begingroup$

Too long for a comment, but I did a simple large brute force computation (the limitation is memory, although going further using disk space wouldn't be impossible).

The unreachable values $k\equiv 3\,\,(\operatorname{mod} 4)$ up to $2\cdot 10^{12}$ are:

4443
13331
39995
80043
119987
240131
359963
719835
720003
720395
1079891
2159507
2160011
2161187
3239675
6478523
6480035
6483563
9719027
19435571
19440107
19450691
29157083
58306715
58320323
58352075
87471251
174920147
174960971
175056227
262413755
524760443
524882915
525168683
787241267
1574281331
1574648747
1575506051
2361723803
4722843995
4723946243
4726518155
7085171411
14168531987
14171838731
14179554467
21255514235
42505595963
42515516195
42538663403
63766542707
127516787891
127546548587
127615990211
191299628123
382550363675
382639645763
382847970635
573898884371
1147651091027
1147918937291
1148543911907
1721696653115

The set is apparently closed under $x\mapsto 3x+2$ and has at least four fundamental solutions, namely $4443$, $80043$, $719835$, and $720003$. The behavior actually seems quite regular. I haven't had time for a proper investigation, but the question doesn't seem impossible. Presumably it would involve constructing an explicit way to reach any $8x+7$, which I assume is what OP did for $128x+127$ (I urge them to post their work). It might also be worth looking at other congruences. Interesting question.

$\endgroup$

Your Answer

Erfan Tavakoli is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.