# An integer sequence defined by recursion

Let's define the following integer sequence. We start with $a_1=3$. Then we define

$$a_{n+1}=a_{n}+(a_{n}\,\text{mod}\,p_n)$$

where $p_n$ is the greatest prime (strictly) less than $a_n$, and $a_{n}\,\text{mod}\,p_n\in\{0,1,2,\ldots,p_n-1\}$. Note that $a_{n}\,\text{mod}\,p_n$ will never be $0$. The first $40$ terms are, if I didn't make any mistakes:

3,4,5,7,9,11,15,17,21,23,27,31,33,35,39,41,45,47,51,55,57,61,63,65,69,71,75,77,81,83,87,91,93,97,105,109,111,113,117,121,129


For example, $a_2=4$ because $2$ is the greatest prime strictly less than $a_1=3$ and $3\equiv 1\,\text{mod}\,2$, so that $a_2=3+1=4$.

Note that the difference between successive terms is either $2$ or $4$ except for the $34$-th and $40$-th terms, where we have $a_{34}-a_{33}=8=a_{40}-a_{39}$. Nevertheless, the difference happens to be always a power of $2$ for these $40$ first terms. In other words $a_{n}\,\text{mod}\,p_n$ is always a power of $2$ for these first $40$ terms.

Now, I wonder if

• $a_{n}\,\text{mod}\,p_n$ will always be a power of $2$?
• will there be infinitely many primes in this sequence?

I searched for this sequence at OEIS, but it seems that it doesn't exist yet.

• If we define $p(x)$ to be the largest prime less than or equal to $x$, then we may rewrite the sequence as $a_{n+1}=2a_n-p(a_n)$. By Bertrand's postulate, $p(a_n)>0.5a_n$. Hence $a_n$ has growth below $1.5^n$. Commented Apr 4, 2016 at 4:20

See vadim123's comment for your second question about whether there are always primes in your sequence. As for your first question, the differences are not always a power of $2$. Here are the first 1000 terms and differences (generated by a few lines of Javascript):

n, a[n], a[n+1]-a[n]
--------------------
1 3 1
2 4 1
3 5 2
4 7 2
5 9 2
6 11 4
7 15 2
8 17 4
9 21 2
10 23 4
11 27 4
12 31 2
13 33 2
14 35 4
15 39 2
16 41 4
17 45 2
18 47 4
19 51 4
20 55 2
21 57 4
22 61 2
23 63 2
24 65 4
25 69 2
26 71 4
27 75 2
28 77 4
29 81 2
30 83 4
31 87 4
32 91 2
33 93 4
34 97 8
35 105 2
36 107 4
37 111 2
38 113 4
39 117 4
40 121 8
41 129 2
42 131 4
43 135 4
44 139 2
45 141 2
46 143 4
47 147 8
48 155 4
49 159 2
50 161 4
51 165 2
52 167 4
53 171 4
54 175 2
55 177 4
56 181 2
57 183 2
58 185 4
59 189 8
60 197 4
61 201 2
62 203 4
63 207 8
64 215 4
65 219 8
66 227 4
67 231 2
68 233 4
69 237 4
70 241 2
71 243 2
72 245 4
73 249 8
74 257 6
75 263 6
76 269 6
77 275 4
78 279 2
79 281 4
80 285 2
81 287 4
82 291 8
83 299 6
84 305 12
85 317 4
86 321 4
87 325 8
88 333 2
89 335 4
90 339 2
91 341 4
92 345 8
93 353 4
94 357 4
95 361 2
96 363 4
97 367 8
98 375 2
99 377 4
100 381 2
101 383 4
102 387 4
103 391 2
104 393 4
105 397 8
106 405 4
107 409 8
108 417 8
109 425 4
110 429 8
111 437 4
112 441 2
113 443 4
114 447 4
115 451 2
116 453 4
117 457 8
118 465 2
119 467 4
120 471 4
121 475 8
122 483 4
123 487 8
124 495 4
125 499 8
126 507 4
127 511 2
128 513 4
129 517 8
130 525 2
131 527 4
132 531 8
133 539 16
134 555 8
135 563 6
136 569 6
137 575 4
138 579 2
139 581 4
140 585 8
141 593 6
142 599 6
143 605 4
144 609 2
145 611 4
146 615 2
147 617 4
148 621 2
149 623 4
150 627 8
151 635 4
152 639 8
153 647 4
154 651 4
155 655 2
156 657 4
157 661 2
158 663 2
159 665 4
160 669 8
161 677 4
162 681 4
163 685 2
164 687 4
165 691 8
166 699 8
167 707 6
168 713 4
169 717 8
170 725 6
171 731 4
172 735 2
173 737 4
174 741 2
175 743 4
176 747 4
177 751 8
178 759 2
179 761 4
180 765 4
181 769 8
182 777 4
183 781 8
184 789 2
185 791 4
186 795 8
187 803 6
188 809 12
189 821 10
190 831 2
191 833 4
192 837 8
193 845 6
194 851 12
195 863 4
196 867 4
197 871 8
198 879 2
199 881 4
200 885 2
201 887 4
202 891 4
203 895 8
204 903 16
205 919 8
206 927 8
207 935 6
208 941 4
209 945 4
210 949 2
211 951 4
212 955 2
213 957 4
214 961 8
215 969 2
216 971 4
217 975 4
218 979 2
219 981 4
220 985 2
221 987 4
222 991 8
223 999 2
224 1001 4
225 1005 8
226 1013 4
227 1017 4
228 1021 2
229 1023 2
230 1025 4
231 1029 8
232 1037 4
233 1041 2
234 1043 4
235 1047 8
236 1055 4
237 1059 8
238 1067 4
239 1071 2
240 1073 4
241 1077 8
242 1085 16
243 1101 4
244 1105 2
245 1107 4
246 1111 2
247 1113 4
248 1117 8
249 1125 2
250 1127 4
251 1131 2
252 1133 4
253 1137 8
254 1145 16
255 1161 8
256 1169 6
257 1175 4
258 1179 8
259 1187 6
260 1193 6
261 1199 6
262 1205 4
263 1209 8
264 1217 4
265 1221 4
266 1225 2
267 1227 4
268 1231 2
269 1233 2
270 1235 4
271 1239 2
272 1241 4
273 1245 8
274 1253 4
275 1257 8
276 1265 6
277 1271 12
278 1283 4
279 1287 4
280 1291 2
281 1293 2
282 1295 4
283 1299 2
284 1301 4
285 1305 2
286 1307 4
287 1311 4
288 1315 8
289 1323 2
290 1325 4
291 1329 2
292 1331 4
293 1335 8
294 1343 16
295 1359 32
296 1391 10
297 1401 2
298 1403 4
299 1407 8
300 1415 6
301 1421 12
302 1433 4
303 1437 4
304 1441 2
305 1443 4
306 1447 8
307 1455 2
308 1457 4
309 1461 2
310 1463 4
311 1467 8
312 1475 4
313 1479 8
314 1487 4
315 1491 2
316 1493 4
317 1497 4
318 1501 2
319 1503 4
320 1507 8
321 1515 4
322 1519 8
323 1527 4
324 1531 8
325 1539 8
326 1547 4
327 1551 2
328 1553 4
329 1557 4
330 1561 2
331 1563 4
332 1567 8
333 1575 4
334 1579 8
335 1587 4
336 1591 8
337 1599 2
338 1601 4
339 1605 4
340 1609 2
341 1611 2
342 1613 4
343 1617 4
344 1621 2
345 1623 2
346 1625 4
347 1629 2
348 1631 4
349 1635 8
350 1643 6
351 1649 12
352 1661 4
353 1665 2
354 1667 4
355 1671 2
356 1673 4
357 1677 8
358 1685 16
359 1701 2
360 1703 4
361 1707 8
362 1715 6
363 1721 12
364 1733 10
365 1743 2
366 1745 4
367 1749 2
368 1751 4
369 1755 2
370 1757 4
371 1761 2
372 1763 4
373 1767 8
374 1775 16
375 1791 2
376 1793 4
377 1797 8
378 1805 4
379 1809 8
380 1817 6
381 1823 12
382 1835 4
383 1839 8
384 1847 16
385 1863 2
386 1865 4
387 1869 2
388 1871 4
389 1875 2
390 1877 4
391 1881 2
392 1883 4
393 1887 8
394 1895 6
395 1901 12
396 1913 6
397 1919 6
398 1925 12
399 1937 4
400 1941 8
401 1949 16
402 1965 14
403 1979 6
404 1985 6
405 1991 4
406 1995 2
407 1997 4
408 2001 2
409 2003 4
410 2007 4
411 2011 8
412 2019 2
413 2021 4
414 2025 8
415 2033 4
416 2037 8
417 2045 6
418 2051 12
419 2063 10
420 2073 4
421 2077 8
422 2085 2
423 2087 4
424 2091 2
425 2093 4
426 2097 8
427 2105 6
428 2111 12
429 2123 10
430 2133 2
431 2135 4
432 2139 2
433 2141 4
434 2145 2
435 2147 4
436 2151 8
437 2159 6
438 2165 4
439 2169 8
440 2177 16
441 2193 14
442 2207 4
443 2211 4
444 2215 2
445 2217 4
446 2221 8
447 2229 8
448 2237 16
449 2253 2
450 2255 4
451 2259 8
452 2267 16
453 2283 2
454 2285 4
455 2289 2
456 2291 4
457 2295 2
458 2297 4
459 2301 4
460 2305 8
461 2313 2
462 2315 4
463 2319 8
464 2327 16
465 2343 2
466 2345 4
467 2349 2
468 2351 4
469 2355 4
470 2359 2
471 2361 4
472 2365 8
473 2373 2
474 2375 4
475 2379 2
476 2381 4
477 2385 2
478 2387 4
479 2391 2
480 2393 4
481 2397 4
482 2401 2
483 2403 4
484 2407 8
485 2415 4
486 2419 2
487 2421 4
488 2425 2
489 2427 4
490 2431 8
491 2439 2
492 2441 4
493 2445 4
494 2449 2
495 2451 4
496 2455 8
497 2463 4
498 2467 8
499 2475 2
500 2477 4
501 2481 4
502 2485 8
503 2493 16
504 2509 6
505 2515 12
506 2527 6
507 2533 2
508 2535 4
509 2539 8
510 2547 4
511 2551 2
512 2553 2
513 2555 4
514 2559 2
515 2561 4
516 2565 8
517 2573 16
518 2589 10
519 2599 6
520 2605 12
521 2617 8
522 2625 4
523 2629 8
524 2637 4
525 2641 8
526 2649 2
527 2651 4
528 2655 8
529 2663 4
530 2667 4
531 2671 8
532 2679 2
533 2681 4
534 2685 2
535 2687 4
536 2691 2
537 2693 4
538 2697 4
539 2701 2
540 2703 4
541 2707 8
542 2715 2
543 2717 4
544 2721 2
545 2723 4
546 2727 8
547 2735 4
548 2739 8
549 2747 6
550 2753 4
551 2757 4
552 2761 8
553 2769 2
554 2771 4
555 2775 8
556 2783 6
557 2789 12
558 2801 4
559 2805 2
560 2807 4
561 2811 8
562 2819 16
563 2835 2
564 2837 4
565 2841 4
566 2845 2
567 2847 4
568 2851 8
569 2859 2
570 2861 4
571 2865 4
572 2869 8
573 2877 16
574 2893 6
575 2899 2
576 2901 4
577 2905 2
578 2907 4
579 2911 2
580 2913 4
581 2917 8
582 2925 8
583 2933 6
584 2939 12
585 2951 12
586 2963 6
587 2969 6
588 2975 4
589 2979 8
590 2987 16
591 3003 2
592 3005 4
593 3009 8
594 3017 6
595 3023 4
596 3027 4
597 3031 8
598 3039 2
599 3041 4
600 3045 4
601 3049 8
602 3057 8
603 3065 4
604 3069 2
605 3071 4
606 3075 8
607 3083 4
608 3087 4
609 3091 2
610 3093 4
611 3097 8
612 3105 16
613 3121 2
614 3123 2
615 3125 4
616 3129 8
617 3137 16
618 3153 16
619 3169 2
620 3171 2
621 3173 4
622 3177 8
623 3185 4
624 3189 2
625 3191 4
626 3195 4
627 3199 8
628 3207 4
629 3211 2
630 3213 4
631 3217 8
632 3225 4
633 3229 8
634 3237 8
635 3245 16
636 3261 2
637 3263 4
638 3267 8
639 3275 4
640 3279 8
641 3287 16
642 3303 2
643 3305 4
644 3309 2
645 3311 4
646 3315 2
647 3317 4
648 3321 2
649 3323 4
650 3327 4
651 3331 2
652 3333 2
653 3335 4
654 3339 8
655 3347 4
656 3351 4
657 3355 8
658 3363 2
659 3365 4
660 3369 8
661 3377 4
662 3381 8
663 3389 16
664 3405 14
665 3419 6
666 3425 12
667 3437 4
668 3441 8
669 3449 16
670 3465 2
671 3467 4
672 3471 2
673 3473 4
674 3477 8
675 3485 16
676 3501 2
677 3503 4
678 3507 8
679 3515 4
680 3519 2
681 3521 4
682 3525 8
683 3533 4
684 3537 4
685 3541 2
686 3543 2
687 3545 4
688 3549 2
689 3551 4
690 3555 8
691 3563 4
692 3567 8
693 3575 4
694 3579 8
695 3587 4
696 3591 8
697 3599 6
698 3605 12
699 3617 4
700 3621 4
701 3625 2
702 3627 4
703 3631 8
704 3639 2
705 3641 4
706 3645 2
707 3647 4
708 3651 8
709 3659 16
710 3675 2
711 3677 4
712 3681 4
713 3685 8
714 3693 2
715 3695 4
716 3699 2
717 3701 4
718 3705 4
719 3709 8
720 3717 8
721 3725 6
722 3731 4
723 3735 2
724 3737 4
725 3741 2
726 3743 4
727 3747 8
728 3755 16
729 3771 2
730 3773 4
731 3777 8
732 3785 6
733 3791 12
734 3803 6
735 3809 6
736 3815 12
737 3827 4
738 3831 8
739 3839 6
740 3845 12
741 3857 4
742 3861 8
743 3869 6
744 3875 12
745 3887 6
746 3893 4
747 3897 8
748 3905 16
749 3921 2
750 3923 4
751 3927 4
752 3931 2
753 3933 2
754 3935 4
755 3939 8
756 3947 4
757 3951 4
758 3955 8
759 3963 16
760 3979 12
761 3991 2
762 3993 4
763 3997 8
764 4005 2
765 4007 4
766 4011 4
767 4015 2
768 4017 4
769 4021 2
770 4023 2
771 4025 4
772 4029 2
773 4031 4
774 4035 8
775 4043 16
776 4059 2
777 4061 4
778 4065 8
779 4073 16
780 4089 10
781 4099 6
782 4105 6
783 4111 12
784 4123 12
785 4135 2
786 4137 4
787 4141 2
788 4143 4
789 4147 8
790 4155 2
791 4157 4
792 4161 2
793 4163 4
794 4167 8
795 4175 16
796 4191 14
797 4205 4
798 4209 8
799 4217 6
800 4223 4
801 4227 8
802 4235 4
803 4239 8
804 4247 4
805 4251 8
806 4259 6
807 4265 4
808 4269 8
809 4277 4
810 4281 8
811 4289 6
812 4295 6
813 4301 4
814 4305 8
815 4313 16
816 4329 2
817 4331 4
818 4335 8
819 4343 4
820 4347 8
821 4355 6
822 4361 4
823 4365 2
824 4367 4
825 4371 8
826 4379 6
827 4385 12
828 4397 6
829 4403 6
830 4409 12
831 4421 12
832 4433 10
833 4443 2
834 4445 4
835 4449 2
836 4451 4
837 4455 4
838 4459 2
839 4461 4
840 4465 2
841 4467 4
842 4471 8
843 4479 16
844 4495 2
845 4497 4
846 4501 8
847 4509 2
848 4511 4
849 4515 2
850 4517 4
851 4521 2
852 4523 4
853 4527 4
854 4531 8
855 4539 16
856 4555 6
857 4561 12
858 4573 6
859 4579 12
860 4591 8
861 4599 2
862 4601 4
863 4605 2
864 4607 4
865 4611 8
866 4619 16
867 4635 14
868 4649 6
869 4655 4
870 4659 2
871 4661 4
872 4665 2
873 4667 4
874 4671 8
875 4679 6
876 4685 6
877 4691 12
878 4703 12
879 4715 12
880 4727 4
881 4731 2
882 4733 4
883 4737 4
884 4741 8
885 4749 16
886 4765 6
887 4771 12
888 4783 24
889 4807 6
890 4813 12
891 4825 8
892 4833 2
893 4835 4
894 4839 8
895 4847 16
896 4863 2
897 4865 4
898 4869 8
899 4877 6
900 4883 6
901 4889 12
902 4901 12
903 4913 4
904 4917 8
905 4925 6
906 4931 12
907 4943 6
908 4949 6
909 4955 4
910 4959 2
911 4961 4
912 4965 8
913 4973 4
914 4977 4
915 4981 8
916 4989 2
917 4991 4
918 4995 2
919 4997 4
920 5001 2
921 5003 4
922 5007 4
923 5011 2
924 5013 2
925 5015 4
926 5019 8
927 5027 4
928 5031 8
929 5039 16
930 5055 4
931 5059 8
932 5067 8
933 5075 16
934 5091 4
935 5095 8
936 5103 2
937 5105 4
938 5109 2
939 5111 4
940 5115 2
941 5117 4
942 5121 2
943 5123 4
944 5127 8
945 5135 16
946 5151 4
947 5155 2
948 5157 4
949 5161 8
950 5169 2
951 5171 4
952 5175 4
953 5179 8
954 5187 8
955 5195 6
956 5201 4
957 5205 8
958 5213 4
959 5217 8
960 5225 16
961 5241 4
962 5245 8
963 5253 16
964 5269 8
965 5277 4
966 5281 2
967 5283 2
968 5285 4
969 5289 8
970 5297 16
971 5313 4
972 5317 8
973 5325 2
974 5327 4
975 5331 8
976 5339 6
977 5345 12
978 5357 6
979 5363 12
980 5375 24
981 5399 6
982 5405 6
983 5411 4
984 5415 2
985 5417 4
986 5421 2
987 5423 4
988 5427 8
989 5435 4
990 5439 2
991 5441 4
992 5445 2
993 5447 4
994 5451 2
995 5453 4
996 5457 8
997 5465 16
998 5481 2
999 5483 4

• As the above shows, evidence for just $100$ values does not suffice in showing the truth of a conjecture. Commented Apr 4, 2016 at 4:44
• @Larara: Your question honestly makes zero sense to me. Is it merely out of curiosity? If really so, you would find things like the twin-prime conjecture, Landau's conjecture, Goldbach's conjecture and Collatz's conjecture interesting. However, all are currently open problems, and in general random number theory conjectures that do not have small counter-examples tend to be extremely hard to prove or disprove. It is even possible that some of these conjectures are neither provable nor disprovable, but we don't know either. Commented Apr 4, 2016 at 4:58
• @Larara: Before you start making conjectures, you should learn programming and also get familiar with some mathematical software such as Sage, so that you can test out your hypotheses yourself rather than asking people here to do it for you. Not that we won't (I just did for your question), but we simply can't do it all the time. And I'd say that most of us aren't interested in random questions about primes unless there is some deep structure involved. Commented Apr 4, 2016 at 5:00
• @Larara: Let me add a bit more about hardness. If a conjecture does not have small counter-examples, but is actually false, then the proof that it is false would necessarily somehow isolate the counter-examples, which is difficult if the theorem statement itself does not have any strange constants. For example, Mertens' conjecture was only proven to be false 100 years after it was first stated, and the proof was non-constructive! Commented Apr 4, 2016 at 5:07
• @Larara: You're welcome. Then I think you'll like very much to read mathoverflow.net/q/15444 and math.stackexchange.com/q/514/21820 and math.stackexchange.com/q/111440/21820. Enjoy! Commented Apr 4, 2016 at 5:35