27
\$\begingroup\$

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

14 Answers 14

9
\$\begingroup\$

Haskell, 57 bytes

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.

\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ Do you post 05AB1E answers from your phone? Cause you do these quick lol. \$\endgroup\$ Mar 31, 2017 at 17:47
  • \$\begingroup\$ @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 :) \$\endgroup\$
    – Emigna
    Mar 31, 2017 at 18:27
4
\$\begingroup\$

Mathematica, 79 bytes

NestList[#+1//.x_/;!PalindromeQ[ToString/@Mod[x,Range@n+1]<>""]:>x+1&,1,n=#-1]&
\$\endgroup\$
4
\$\begingroup\$

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));
}

\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
2
  • \$\begingroup\$ you can drop the entire string conversion \$\endgroup\$
    – Rod
    Mar 31, 2017 at 16:10
  • \$\begingroup\$ @Rod Thanks, but I believe that would fail on input 12 due to the strange rule that [1, 10, 11] is considered a palindrome \$\endgroup\$ Mar 31, 2017 at 16:46
3
\$\begingroup\$

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)
\$\endgroup\$
0
3
\$\begingroup\$

Scala, 90 86 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)
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Welcome to PPCG! \$\endgroup\$ Apr 2, 2017 at 13:23
  • \$\begingroup\$ 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 ! \$\endgroup\$
    – norbjd
    Apr 3, 2017 at 9:13
  • \$\begingroup\$ Yes, unnamed functions are allowed, provided you don't need the name for a recursive call or something like that. \$\endgroup\$ Apr 3, 2017 at 9:15
  • \$\begingroup\$ Great, edited :) \$\endgroup\$
    – norbjd
    Apr 3, 2017 at 9:32
2
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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.
\$\endgroup\$
1
\$\begingroup\$

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);
\$\endgroup\$
1
\$\begingroup\$

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.
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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:
      ɗ  -   Combine the previous three links into a dyad
             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?
           
\$\endgroup\$
0
\$\begingroup\$

Japt, 13 bytes

@õ!uX ÅêS}jU1

Try it or run all test cases

@õ!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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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