# Palindromic Residue

Today, as I'm writing this, is March 31st. In the US, this is 3/31. I was playing around with 331 as a number to come up with a challenge, and found that its residues (modulo small numbers) is palindromic. 331%2=1, 331%3=1, 331%4=3, 331%5=1, 331%6=1 (11311).

Your challenge here is, when given an integer n > 2, output the first n positive numbers that have palindromic residue when taken modulo [2,n].

For example, for input 7, the output should be 1, 42, 43, 140, 182, 420, 421. Here's the chart explaining why that's the case:

        mod
num | 2 3 4 5 6 7
-----------------
1 | 1 1 1 1 1 1
42 | 0 0 2 2 0 0
43 | 1 1 3 3 1 1
140 | 0 2 0 0 2 0
182 | 0 2 2 2 2 0
420 | 0 0 0 0 0 0
421 | 1 1 1 1 1 1


## Input

A single positive integer n with n > 2 in any convenient format.

## Output

The resulting array/list of the first n palindromic residues, as outlined above. Again, in any suitable format.

## Rules

• For n > 10, assume the residue list to be flattened before checking whether it's a palindrome. That is, [1, 10, 11] is palindromic, but [1, 10, 1] is not.
• Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
• If possible, please include a link to an online testing environment so other people can try out your code!
• Standard loopholes are forbidden.
• This is so all usual golfing rules apply, and the shortest code (in bytes) wins.

### Examples

[input]
[output]

3
[1, 6, 7]

4
[1, 4, 5, 8]

5
[1, 50, 60, 61, 110]

6
[1, 30, 31, 60, 61, 90]

7
[1, 42, 43, 140, 182, 420, 421]

8
[1, 168, 169, 336, 337, 504, 505, 672]

9
[1, 2520, 2521, 5040, 5041, 7560, 7561, 10080, 10081]

10
[1, 280, 281, 560, 1611, 1890, 1891, 2170, 2171, 2241]

11
[1, 22682, 27720, 27721, 50402, 55440, 55441, 78122, 83160, 83161, 105842]

• Is the output supposed to be ordered? Mar 31, 2017 at 15:24
• @Arnauld It doesn't need to be, no, provided that it includes only the first n elements. Mar 31, 2017 at 15:27
• arrgh ... your challenge = your rules, but "[1, 10, 11] is palindromic, but [1, 10, 1] is not" seems so mathematically wrong. Mar 31, 2017 at 16:25
• @GregMartin Stringy palindromes, not mathy palindromes. ;-) Mar 31, 2017 at 16:34
• grr. The whole stringy instead of mathy palindrome makes this a thousand times harder in certain languages. Oh well. Mar 31, 2017 at 17:06

f n=take n[x|x<-[1..],(==)=<<reverse$show.mod x=<<[2..n]]  Usage example: f 4 -> [1,4,5,8]. Try it online! The first =<< is in function context and translates to the lambda \x -> reverse x == x and the second =<< is in list context and equivalent to concatMap, i.e. map-and-flatten-one-list-level. # 05AB1E, 12 bytes µN2¹Ÿ%JÂQD½–  Try it online! Explanation µ # until counter equals input do: N # push current iterations number % # modulus each in 2¹Ÿ # range [2 ... input] J # joined to string ÂQ # equals it's reverse D # duplicate ½ # if true, increase counter – # if true print iteration number  • Do you post 05AB1E answers from your phone? Cause you do these quick lol. Mar 31, 2017 at 17:47 • @carusocomputing: Very seldom as a lot of the characters in cp-1252 are annoying to type/copy-paste on the phone. This one popped up right before I checked my computer after dinner, so I had pretty good timing :) Mar 31, 2017 at 18:27 ## Mathematica, 79 bytes NestList[#+1//.x_/;!PalindromeQ[ToString/@Mod[x,Range@n+1]<>""]:>x+1&,1,n=#-1]&  ## JavaScript (ES6), 104 bytes f=(n,x=(k=--n,2))=>k?([...Array(n)].map(_=>(r=x%++i+r,x%i),i=1,r='').join==r?k--&&x+' ':'')+f(n,x+1):1  ### Demo NB: Because of the numerous recursive calls, this will crash for n > 8 on Firefox or n > 10 on Chrome. f=(n,x=(k=--n,2))=>k?([...Array(n)].map(_=>(r=x%++i+r,x%i),i=1,r='').join==r?k--&&x+' ':'')+f(n,x+1):1 for(n = 2; n < 9; n++) { console.log(n, '=>', f(n)); } # Python 2, 98 97 bytes n=input();i=j=0 while i<n: j+=1;l='' for k in range(2,n+1):l+=j%k if l==l[::-1]:i+=1;print j  Try it Online! • you can drop the entire string conversion – Rod Mar 31, 2017 at 16:10 • @Rod Thanks, but I believe that would fail on input 12 due to the strange rule that [1, 10, 11] is considered a palindrome Mar 31, 2017 at 16:46 # MATL, 19 bytes Thanks to @AdmBorkBork for pointing out a mistake in an earlier version of the code, now corrected @Gq:Q\VXztP=?@]NG<  Try it online! ### Explanation  % Do...while @ % Push iteration index, starting at 1 Gq:Q % Push [2 3 ... n], where n is the input \ % Modulo, element-wise V % Convert to string. Numbers are separated by spaces Xz % Remove spaces tP % Duplicate, flip = % Equal? (element-wise) ? % If all results were true @ % Push current iteration index. It is one of the sought numbers ] % End N % Push number of elements in stack G % Push input n < % Less than? This is the loop condition % End (implicit). Display (implicit)  # Scala, 9086 82 bytes (n:Int)=>Stream.from(1)filter{i=>val d=(2 to n)map(i%)mkString;d.reverse==d}take(n)  ## Explanation Stream.from(1) // From an infinite Stream starting from 1, filter ( i => { // keep only elements matching the next condition : val d=(2 to n)map(i%)mkString; // Generate residues and convert to String, d.reverse==d // return true if palindrom, false otherwise })take(n) // Finally, take the n first elements matching the condition  ## Test cases val f = (n:Int)=>... // assign function (3 to 11).foreach { i => println(i + "\n" + f(i).mkString(", ") + "\n") }  ## Results 3 1, 6, 7 4 1, 4, 5, 8 5 1, 50, 60, 61, 110 6 1, 30, 31, 60, 61, 90 7 1, 42, 43, 140, 182, 420, 421 8 1, 168, 169, 336, 337, 504, 505, 672 9 1, 2520, 2521, 5040, 5041, 7560, 7561, 10080, 10081 10 1, 280, 281, 560, 1611, 1890, 1891, 2170, 2171, 2241 11 1, 22682, 27720, 27721, 50402, 55440, 55441, 78122, 83160, 83161, 105842  ## Edits ### #1 (90 => 86) • anonymous function ### #2 (86 => 82) • remove useless dot characters after parenthesis or bracket (ex. : (2 to n).map(%i) => (2 to n)map(%i) • Welcome to PPCG! Apr 2, 2017 at 13:23 • Thanks! I was wondering if I could change def f(n:Int)= to (n:Int)=>, since it also defines a function (but without name). It saves 4 bytes ! Apr 3, 2017 at 9:13 • Yes, unnamed functions are allowed, provided you don't need the name for a recursive call or something like that. Apr 3, 2017 at 9:15 • Great, edited :) Apr 3, 2017 at 9:32 # Jelly, 12 bytes %Ð€ḊDFŒḂ 1ç#  ### How? 1ç# - Main link: n 1 - initialise "i" at 1 # - increment i and yield a list of the first n truthful results of: ç - last link (1) as a dyad %Ð€ḊDFŒḂ - Link 1, test a value "i" for mod [2,n] being palindromic: i, n Ð€ - for each, mapped over the right argument, i.e. for j = 1 to n: % - i modulo j Ḋ - dequeue, i.e. discard the modulo 1 result D - convert to decimal list (vectorises) F - flatten into one list ŒḂ - is palindromic?  Try it online! ## CJam, 28 bytes 0ri:N{{)_N),2>f%s_W%#}g_p}*;  Try it online! ### Explanation 0 e# Push 0, the value we'll repeatedly increment to search for valid outputs. ri:N e# Read input, convert to integer, store in N. { e# Run this block N times... { e# Run this block until the condition is true, which will find the next e# number with palindromic residues... )_ e# Increment and duplicate. N),2> e# Push [2 3 ... N]. f% e# Take the current value modulo each of these. s e# Flatten them into a single string. _W% e# Duplicate and reverse. # e# Try to find the reverse in the original. A common way to compute e# "not equal" for strings of the same length. }g _p e# Print a copy of the result. }* ; e# Discard the final result to prevent printing it twice.  # PHP, 93 Bytes for(;$x<$a=$argn;$s="")for($i=1,++$n;$i++<$a;)if($i==$a&strrev($s.=$n%$i)==$s)echo$n._.!++$x;  Online Version 2 Loops Output as string Expanded for(;$x<$a=$argn;$s="") for($i=1,++$n;$i++<$a;) if($i==$a&strrev($s.=$n%$i)==$s)echo$n._.!++$x;  ## PHP 130 Bytes for(;count($r)<$a=$argn;$s=[])for($i=1,++$n;$i++<$a;){$s[]=$n%$i;if(count($s)==$a-1&strrev($j=join($s))==$j)$r[]=$n; }print_r($r);


Online Version 2 Loops

Expanded

for(;count($r)<$a=$argn;$s=[])
for($i=1,++$n;$i++<$a;){
$s[]=$n%$i; if(count($s)==$a-1&strrev($j=join($s))==$j)$r[]=$n;
}
print_r($r);  ## PHP, 139 Bytes with 1 loop for($i=$n=1;count($r)<($a=$argn)&$i++<$a;){$s[]=$n%$i;if(count($s)==$a-1){if(strrev($j=join($s))==$j)$r[]=$n;$n++;$s=[];$i=1;}}print_r($r);


Online Version 1 Loop

Run with

echo '<string>' | php -nR '<code>'


Expanded

for($i=$n=1;count($r)<($a=$argn)&$i++<$a;){$s[]=$n%$i;
if(count($s)==$a-1){
if(strrev($j=join($s))==$j)$r[]=$n;$n++;
$s=[];$i=1;
}
}
print_r($r);  ## QBIC, 48 bytes :{A=G[2,a|A=A+!q%b$]~A=_fA||h=h+1?q]q=q+1~h=a|_X


Beats Mathematica! Sample run:

Command line: 10
1
280
281
560
1611
1890
1891
2170
2171
2241


Explanation:

:{          Get 'a' from the command line, start an inf. loop
A=G         Clear out whatever's in A$[2,a| For each of the numbers we want to modulo A=A+ Add to A$
q%b       our current number MODULO te loop iterator
!   \$      cast to string
]           NEXT
~A=_fA|     If the string of remainders is a palindrome (_f ... | is Reverse())
|h=h+1      THEN h=h+1 (h starts at 0) - this counts how many hits we've had
?q            also, print the number with the palindromic remainder
]           END IF
q=q+1       Test the next number
~h=a|_X     If we've had 'a' hits, quit.
The last IF and the infinite loop are closed implicitly.


# Japt, 26 bytes

L³o fR{C=Uò2@R%XÃ¬ ¥CwÃj1U


Try it online! Takes a few seconds on all inputs, so be patient please.

This would be considerably shorter (and faster) if there were a built-in to get the first N numbers satisfying some condition:

R{C=Uò2@R%XÃ¬ ¥Cw}aU


# Jelly, 8 bytes

1%ⱮḊŒḂɗ#


Try it online!

## How it works

1%ⱮḊŒḂɗ# - Main link. Takes n on the left
1        - Set the return value to 1
# - Count up i = 1, 2, ..., and return the first n which return true:
with i on the left and n on the right:
Ɱ      -     For each integer m in 1, 2, ..., n:
%       -       i % m
Ḋ     -     Remove i % 1
ŒḂ   -     Is palindromic?



# Japt, 13 bytes

@õ!uX ÅêS}jU1

@õ!uX ÅêS}jU1     :Implicit input of integer U
@                 :Function taking an integer X as argument
õ                :  Range [1,U]
!uX             :  Mod X by each
Å           :  Slice off the first
êS         :  Is palindrome?
}        :End function
jU1     :Starting with 1, return the first U integers that return true